Jonathan Conroy

Hsien-Chih Chang, Jonathan Conroy, Zihan Tan et al.

In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\varepsilon$ distortion regimes. Furthermore, the distance sketches themselves are planar graphs. First, we show that every unweighted string graph $G$ has an $O(1)$-distortion planar emulator: that is, there exists an edge-weighted planar graph $H$ containing every vertex in $G$, such that every pair of vertices $(u,v)$ satisfies $δ_G(u,v) \le δ_H(u,v) \le O(1) \cdot δ_G(u,v)$. Furthermore, we show that for any constant $\varepsilon > 0$, there is an edge-weighted planar graph $H'$ such that every pair of vertices $(u,v)$ satisfies $δ_G(u,v) \le δ_{H'}(u,v) \le (1+\varepsilon) \cdot δ_G(u,v) + O(\varepsilon^{-4}\textrm{poly}\log n)$. No previous constructions of sparse distance sketches were known even for intersection graphs of simple shapes like axis-parallel rectangles or fat convex polygons. As applications, we construct the first $(1+\varepsilon, +O(1))$ mixed-distortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive $+(\varepsilonΔ+O(1))$-distortion embedding of string graphs $G$ with diameter $Δ$ into graphs of constant treewidth $O(\varepsilon^{-4})$.

Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy et al.

Given a weighted digraph $G$, a $(t,g,μ)$-DAG cover is a collection of $g$ dominating DAGs $D_1,\dots,D_g$ such that all distances are approximately preserved: for every pair $(u,v)$ of vertices, $\min_id_{D_i}(u,v)\le t\cdot d_{G}(u,v)$, and the total number of non-$G$ edges is bounded by $|(\cup_i D_i)\setminus G|\le μ$. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of \emph{Steiner} DAG cover, where the DAGs are allowed to contain Steiner points. We obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a $(1,2,\tilde{O}(n\cdot tw))$-Steiner DAG cover. For planar digraphs we provide a $(1+\varepsilon,2,\tilde{O}_\varepsilon(n))$-Steiner DAG cover. We also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth $1$ with stretch $t<2$ and sub-quadratic number of extra edges requires $Ω(\log n)$ DAGs.

Sujoy Bhore, Jonathan Conroy, Arnold Filtser

A $t$-spanner of a point set $X$ in a metric space $(\mathcal{X}, δ)$ is a graph $G$ with vertex set $P$ such that, for any pair of points $u,v \in X$, the distance between $u$ and $v$ in $G$ is at most $t$ times $δ(u,v)$. We study the problem of maintaining a spanner for a dynamic point set $X$ -- that is, when $X$ undergoes a sequence of insertions and deletions -- in a metric space of constant doubling dimension. For any constant $\varepsilon>0$, we maintain a $(1+\varepsilon)$-spanner of $P$ whose total weight remains within a constant factor of the weight of the minimum spanning tree of $X$. Each update (insertion or deletion) can be performed in $\operatorname{poly}(\log Φ)$ time, where $Φ$ denotes the aspect ratio of $X$. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space.

Jonathan Conroy, Christopher Thierauf, Parker Rule et al.

Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradiation. In this paper, we propose a purpose-made inexpensive robotic platform with off-the-shelf components and standard navigation software that, with a novel algorithm for finding optimal irradiation locations, addresses both shortcomings to offer affordable and efficient solutions for UVC irradiation. We demonstrate in simulations the efficacy of the algorithm and show a prototypical run of the autonomous integrated robotic system in an indoor environment. In our sample instances, our proposed algorithm reduces the time needed by roughly 30\% while it increases the coverage by a factor of 35\% (when compared to the best possible placement of a static light).