Theory Work

Here are selected published and unpublished works that I have contributed to in discrete and computational geometry. The current overarching theme of my work has been in finding graph theoretical structures within geometric set systems to find efficient algorithms for packing and covering.

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

Coauthors: Prahlad Narasimham Kasthurirangan, Joseph SB Mitchell, and Valentin Polishchuk

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 appeared in FOCS 2023.

Covering and Partitioning Complex Objects with Small Pieces

Coauthors: Anders Aamand, Mikkel Abrahamsen, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph SB Mitchell, Valentin Polishchuk, Jack Stade

We explore a natural problem that is motivated by manufacturing: given a large 3D object P and a small 3D printer, what is the fewest number of pieces that we can 3D print that we can use to assemble P. We show that even with the limitation that all pieces are subsets of P and that they must fit into the 3D printer upright (fit inside an axis-aligned cube) then the problem is as difficult to approximate as Set Cover. If we drop the dimension down to 2D with the same limitations, then the problem admits a PTAS, but still remains NP-hard. This paper is available on arxiv, and appeared in SoCG 2026.

Single Criterion Approximation for Metric r-Dominating Set

Coauthor: Hsien-Chih Chang

We provide a unifying structural property of ball systems in planar (and more generally minor-free) graphs, known as a support graph. The particular properties of our support graph is that if the underlying graph that the balls live on forbids a minor, then so does the support graph. This structural property explains some results in prior work, and can also be used as an ingredient for making progress on a long-standing open problem: Find a minimum weight distance r-dominating set in a planar metric. We show the first improvement past O(log n) for the single criterion case. This paper is available on arxiv, and appeared in SoCG 2026.

Decomposing a Simple Polygon Using Geodesic Balls

Coauthor: Prahlad Narasimhan Kasthurirangan

We address the problem of finding a minimum number of unit geodesic disks needed to cover a simple polygon P. Here a unit geodesic disk is a set described by a point, radius pair (c,r), where the ball is all points within walking distance r of the center point c. So our goal is to find a set of center points such that no point in P is more than a unit distance away from at least 1. For this problem, we give the first known algorithm to give any approximation guarantee. Our algorithm runs polynomial time, but there is currently no known exact algorithm even with exponential time allowed. We achieve a 9-approximation using a greedy-style aproach. We also address the problem of partitioning a polygon into the fewest regions of unit geodesic diameter, which had an existing 72 approximation. For this problem we are able to use a similar greedy-style approach to get a 15. This paper is available on arxiv and appeared in ESA 2026.

Collapsing the Hidden-Set Convex-Cover Inequality

Coauthor: Eric Chiu

We show the first known example of a simple polygon for which the hidden set number and the convex cover number diverge. Our example also falls into several subcategories of polygons, namely it is orthogonal, monotone, and star-shaped. On the positive side, we give simple algorithms for finding optimal hidden sets and optimal convex covers of spiral polygons and histogram polygons, both running in linear time. The original version of this work was presented at CG:YRF 2022, but an extended version, including a proof that it is NP-hard to decide if a polygon has diverging values for hidden set number and convex cover number, is provided here.

Practical Algorithms for Decomposing Objects into Small Components

Coauthors: Mikkel Abrahamsen, Prahlad Narasimhan Kasthurirangan, Mayank Goswami, Joseph Mitchell, Michael Perk, and Valentin Polishchuk

While the PTAS provided in our SoCG 2026 paper for finding a minimum cover of a polygon with pieces that fit in an axis-aligned square (3D printer bed) manages to achieve a factor of (1+ε), to achieve this factor, the runtime required is highly impractical, even for large values of ε. In contrast, we show that if a simple 4-approximation is acceptable, then we can reduce the runtime down to nearly O(n * OPT), where OPT is the size of the solution. Additionally, we are able to give a simple 2-approximation when the connectivity constraint is dropped, and a 4-approximation for the corresponding case in 3D. All of these algorithms are both implementable and, for the 2D cases, implemented. We run our implementations on several benchmark cases and provide them as open source. This paper is avalaible here and appeared in CG:YRF 2026.

Cache Oblivious Parallel Convex Hull in the Binary Forking Model

Coauthors: Rezaul Chowdhury, Shih-Yu Tsai, and Yimin Zhu

We provide a novel convex hull algorithm for presorted input which achieves optimal performance within the intersection of two highly restrictive models of computation: the binary forking model for parallel computation and the cache oblivious model for cache performance. This paper is available on arxiv.

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.gr@dartmouth.edu