Eunjin Oh

Seongbin Park, Eunjin Oh

In this paper, we study the many-to-many matching problem on planar point sets with integer coordinates: Given two disjoint sets $R,B \subset [Δ]^2$ with $|R|+|B|=n$, the goal is to select a set of edges between $R$ and $B$ so that every point is incident to at least one edge and the total Euclidean length is minimized. In the general case that $R$ and $B$ are point sets in the plane, the best-known algorithm for the many-to-many matching problem takes $\tilde{O}(n^2)$ time. We present an exact $\tilde{O}(n^{1.5} \log Δ)$ time algorithm for point sets in $[Δ]^2$. To the best of our knowledge, this is the first subquadratic exact algorithm for planar many-to-many matching under bounded integer coordinates.

Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist et al.

We study the problem of computing a shortest tour that visits a sequence of $k$ polygons $P_1,\dots, P_k$ with a total number of $n$ vertices. A tour is an oriented curve such that there exist points $p_i\in P_i$ for all $i$ where $p_i$ appears not after $p_{i+1}$. In a seminal paper Dror, Efrat, Lubiw, and Mitchell (STOC 2003) considered the problem under $L_2$ distance, and gave $\widetilde O(nk)$ and $\widetilde O(nk^2)$ algorithms for disjoint and intersecting convex polygons, respectively. This paper considers the orthogonal setting, where the input polygons have axis-aligned edges and the distance metric is the Manhattan distance. We obtain the following results: - as our main contribution, a truly subquadratic $\widetilde O(n^{2-\frac{1}{48}})$ algorithm when consecutive polygons in the sequence are disjoint; - an $\widetilde O(n)$ algorithm for ortho-convex polygons when consecutive polygons are disjoint; - an $O(n)$ algorithm for axis-aligned rectangles; - $\widetilde O(n^2)$ and $\widetilde O(n^{1.5}k^2)$ algorithms without restrictions. Our algorithms build on a wide range of techniques, including additively weighted Voronoi diagrams, rectangle decompositions, persistent data structures, and dynamic distance oracles for weighted planar graphs.

Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla et al.

Given a simple polygon $P$ with $n$ vertices, we consider the problem of constructing a data structure for visibility queries: for any query point $q \in P$, compute the visibility polygon of $q$ in $P$. To obtain $O(\log n + k)$ query time, where $k$ is the size of the visibility polygon of $q$, the previous best result requires $O(n^3)$ space. In this paper, we propose a new data structure that uses $O(n^{2+ε})$ space, for any $ε> 0$, while achieving the same query time. If only $O(n^2)$ space is available, the best known result provides $O(\log^2 n + k)$ query time. We improve this to $O(\log n \log \log n + k)$ time. When restricted to $o(n^2)$ space, the only previously known approach, aside from the $O(n)$-time algorithm that computes the visibility polygon without preprocessing, is an $O(n)$-space data structure that supports $O(k \log n)$-time queries. We construct a data structure using $O(n \log n)$ space that answers visibility queries in $O(n^{1/2+ε} + k)$ time. In addition, for the special case in which $q$ lies on the boundary of $P$, we build a data structure of $O(n \log n)$ space supporting $O(\log^2 n + k)$ query time; alternatively, we achieve $O(\log n + k)$ query time using $O(n^{1+ε})$ space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.

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.