Theory Work

Here is a collection of some papers I've written related to discrete and computational geometry. I hope to expand this list much more in the future as some works I plan on publishing, so they will appear here only after I get the go-ahead.

Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon

In this paper, we give subcubic time approximation algorithms for convex cover and hidden set for simple polygons. This is the first constant factor approximation for both problems, and the first non-trivial approximation algorithm for hidden set that is known. Both problems have previously been proven to be APX-hard, so these algorithms imply they are in fact APX-complete. This paper is avalaible here and on Valentin's website

Convex Cover and Hidden Set in Funnel Polygons

In this paper, I give linear time algorithms for convex cover, hidden set, and hidden vertex set restricted to funnel polygons. From this, I am able to achieve 2-approximations for the same problems in pseudotriangles. I also give an example polygon where placing hidden points along the boundary of a pseudotriangle gives suboptimal solutions, implying that a very different method is required. This paper is also available on arxiv:

Cache-Oblivious Parallel Convex Hull in the Binary Forking Model

In this paper, I and other members of the SBU TEALab investigated the Convex Hull problem, specifically in 2D. We developed two parallel algorithms, one for presorted points and one for unsorted points, which achieve optimal cache complexity under the cache-oblivious model and optimal or state of the art span for the Binary Forking Model. This paper is also available on arxiv:

Collapsing the Hidden Set-Convex Cover Inequality

In this paper, I and my colleague Eric Chiu show a polygon for which hidden set and convex cover are declaratively distinct values and show two classes of polygons for which they are equivalent. The two classes also have linear time algorithms for finding both a hidden set and convex cover. This paper was accepted to CG Week's Young Researcher's Forum. Here is an extended version of the paper.

Polyhedral Nonexistence from Graphs

In this paper, inspired by coursework from Joseph S.B. Mitchell's Computational geometry class at SBU, I discuss some limitations on the existence of certain polyhedra using graph theory. The full paper is available here

and on Research Gate. Citation is available as BibTex here.

BLANK

My Other Projects

Here is a collection of other projects that I feature on my Github. For the full list of my repositories, go to my profile at https://github.com/Rajalo.

Travelling Salesperson Tour Calculator

This program implements a branch and bound technique to find the optimal travelling salesperson tour for an inputted set of points. I wanted to give it a more retro feel, so I decided to do pixel art for every component, even the inputs for coordinates. The program has a hard limit on the number of points that can be inputted, 20. It allows users to scroll vertically and horizontally through an infinite grid. The user can also add specific points using the coordinate input boxes.
To download, the release is here: https://github.com/Rajalo/TSPTourCalculator/releases/tag/v1.0
And the full repository is here https://github.com/Rajalo/TSPTourCalculator

Travelling Salesperson Approximations in Python

This repository is a collection of implementations of approximation algorithms for the optimal Travelling Salesperson tour for given points in the plane. I developed these implementations as part of a related research paper. Currently that paper is not complete, so I will link that here as well once that is finished.
The full repository is here https://github.com/Rajalo/TSP-Approximation-Algorithms-in-Python

Club Management Systems

This repository is a collection of Google Apps Script systems I made to help run clubs in high school and my freshman year of college. They automated some of the more mundane tasks of leadership, most centrally writing emails for notifying the membership of weekly goings-ons.
The full repository is here https://github.com/Rajalo/Club-Management-Systems

Dream Run

This is a game I made back in AP Computer Science. It's an arcade style game following a blue man's futile quest to get his jacket back from a flying trickster.
The full repository is here https://github.com/Rajalo/Dream-Run

RoseField Farms

This is a game I made my freshman year of college. It's an arcade style game following a farmer's attempts to keep a rose business afloat despite the shenanigans of local animals.
The full repository is here https://github.com/Rajalo/RoseField-Farms

Pixel Art Gallery

A fun hobby I've gotten into is game development. Often I like to sketch out my ideas for games by trying to create pixel art for the game to see how I like the idea. Here are some excerpts of that work. At the end I included the pixel art from my TSP Calculator, which is on my Github.

Contact Information

reilly.browne@stonybrook.edu