Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of 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,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(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.

In this paper, we study the problem of constructing a (1/ε)-well-separated pair decomposition (WSPD) for a point set of size n in the Massively Parallel Computation (MPC) model, where multiple machines work in parallel and communicate in synchronous rounds. We present an O(1)-round MPC algorithm that constructs a O(1/ε)-WSPD of size (1/ε)^O(ddim) ⋅ Õ(n) for point sets in a metric space of a constant doubling dimension ddim, with high probability, using (1/ε)^O(ddim) ⋅ Õ(n) total space and O(n^δ) space per machine for a constant δ ∈ (0,1). In the d-dimensional Euclidean space, we can improve the size of the WSPD and the total space to (1/ε)^O(d) n. This improves the best-known algorithm [FOCS'93] for computing a WSPD which requires O(log n) rounds and works only in Euclidean spaces. As a consequence, the following problems can be solved in O(1) rounds in the MPC model: computing a (1+ε)-spanner, a (1-ε)-approximation of the diameter, the closest pair, and the k-nearest neighbors (k-NN). While our k-NN algorithm is specific to Euclidean space, the other three problems can be solved in both Euclidean and doubling metric spaces.

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 ∈ 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³) 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²) space is available, the best known result provides O(log² n + k) query time. We improve this to O(log n log log n + k) time. When restricted to o(n²) 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² 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.

We study the problem of computing a shortest tour that visits a sequence of k polygons P₁,…,P_k with a total number of n vertices. A tour is an oriented curve such that there exist points p_i ∈ 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₂ distance, and gave Õ(nk) and Õ(nk²) algorithms for disjoint and intersecting convex polygons, respectively. In this paper, we consider the orthogonal setting (with orthogonal polygons and Manhattan distance) and obtain the following results: - a truly subquadratic Õ(n^{2-1/48}) algorithm when consecutive polygons in the sequence are disjoint; - an Õ(n) algorithm for ortho-convex polygons when consecutive polygons are disjoint; - an O(n) algorithm for axis-aligned rectangles; - Õ(n²) and Õ(n^{1.5}k²) 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.

Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Pre-assignment for Uniquification of Minimum Vertex Cover problem (shortly PAU-VC) is the problem, for given a graph G, to find a minimum set S of vertices in G such that there is a unique minimum vertex cover of G containing S. We show that PAU-VC is fixed parameter tractable parameterized by clique-width, which improves an exponential algorithm for trees given by Horiyama et al. Among natural graph classes with unbounded clique-width, we show that the problem can be solved in polynomial time on split graphs and unit interval graphs.

In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in the plane. Here, the weight of an edge is defined as the Euclidean distance between the centers of the disks corresponding to the endpoints of the edge. Given a family of $n$ disks in the plane whose radii lie in $[1,Ψ]$ and a source disk, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^2 n \log Ψ)$ time. Moreover, in the case that the radii of disks are arbitrarily large, we can compute a shortest path tree from a source vertex in the weighted disk graph in $O(n\log^4 n)$ time. This improves the best-known algorithm running in $O(n\log^6 n)$ time presented in ESA'23.

In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size $n$ in a discrete space $[Δ]^d$, where queries can be made to an oracle that responds to orthogonal range counting requests. The query complexity of an optimization problem is measured by the number of oracle queries required to compute an estimator for the problem. We investigate two problems in this framework, the Euclidean Minimum Spanning Tree (MST) and Earth Mover Distance (EMD). For EMD, we show the existence of an estimator that approximates the cost of EMD with $O(\log Δ)$-relative error and $O(\frac{nΔ}{s^{1+1/d}})$-additive error using $O(s\polylog Δ)$ range counting queries for any parameter $s$ with $1\leq s \leq n$. Moreover, we prove that this bound is tight. For MST, we demonstrate that the weight of MST can be estimated within a factor of $(1 \pm \eps)$ using $\tilde{O}(\sqrt{n})$ range counting queries.

In this paper, we present approximate distance and shortest-path oracles for fault-tolerant Euclidean spanners motivated by the routing problem in real-world road networks. A fault-tolerant Euclidean spanner for a set of points in Euclidean space is a graph in which, despite the deletion of small number of any points, the distance between any two points in the damaged graph is an approximation of their Euclidean distance. Given a fault-tolerant Euclidean spanner and a small approximation factor, our data structure allows us to compute an approximate distance between two points in the damaged spanner in constant time when a query involves any two points and a small set of failed points. Additionally, by incorporating additional data structures, we can return a path itself in time almost linear in the length of the returned path. Both data structures require near-linear space.

In this paper, we consider the Cycle Packing problem on unit disk graphs defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set of $k$ vertex-disjoint cycles of G if it exists. Our algorithm runs in time $2^{O(\sqrt k)}n^{O(1)}$. This improves the $2^{O(\sqrt k\log k)}n^{O(1)}$-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis.

We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set $S$ of $n$ points in the plane and the goal is to find two smallest congruent disks whose union contains all points of $S$. A longstanding open problem has been to obtain an $O(n\log n)$-time algorithm for planar two-center, matching the $Ω(n\log n)$ lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in $O(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.

An outerstring graph is the intersection graph of curves lying inside a disk with one endpoint on the boundary of the disk. We show that an outerstring graph with $n$ vertices has treewidth $O(α\log n)$, where $α$ denotes the arboricity of the graph, with an almost matching lower bound of $Ω(α\log (n/α))$. As a corollary, we show that a $t$-biclique-free outerstring graph has treewidth $O(t(\log t)\log n)$. This leads to polynomial-time algorithms for most of the central NP-complete problems such as \textsc{Independent Set}, \textsc{Vertex Cover}, \textsc{Dominating Set}, \textsc{Feedback Vertex Set}, \textsc{Coloring} for sparse outerstring graphs. Also, we can obtain subexponential-time (exact, parameterized, and approximation) algorithms for various NP-complete problems such as \textsc{Vertex Cover}, \textsc{Feedback Vertex Set} and \textsc{Cycle Packing} for (not necessarily sparse) outerstring graphs.

In this paper, we study fundamental parameterized problems such as $k$-Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk graphs. Given a vertex set $V$ changing dynamically under vertex insertions and deletions, our goal is to maintain data structures so that the aforementioned parameterized problems on the unit disk graph induced by $V$ can be solved efficiently. Although dynamic parameterized problems on general graphs have been studied extensively, no previous work focuses on unit disk graphs. In this paper, we present the first data structures for fundamental parameterized problems on dynamic unit disk graphs. More specifically, our data structure supports $2^{O(\sqrt{k})}$ update time and $O(k)$ query time for $k$-Path/Cycle. For the other problems, our data structures support $O(\log n)$ update time and $2^{O(\sqrt{k})}$ query time, where $k$ denotes the output size.

In this paper, we study a \emph{multicut-mimicking network} for a hypergraph over terminals $T$ with a parameter $c$. It is a hypergraph preserving the minimum multicut values of any set of pairs over $T$ where the value is at most $c$. This is a new variant of the multicut-mimicking network of a graph in [Wahlström ICALP'20], which introduces a parameter $c$ and extends it to handle hypergraphs. Additionally, it is a natural extension of the \emph{connectivity-$c$ mimicking network} introduced by [Chalermsook et al. SODA'21] and [Jiang et al. ESA'22] that is a (hyper)graph preserving the minimum cut values between two subsets of terminals where the value is at most $c$. We propose an algorithm for a hypergraph that returns a multicut-mimicking network over terminals $T$ with a parameter $c$ having $|T|c^{O(r\log c)}$ hyperedges in $p^{1+o(1)}+|T|(c^r\log n)^{\tilde{O}(rc)}m$ time, where $p$ and $r$ are the total size and the rank, respectively, of the hypergraph.

In this paper, we study the maximum clique problem on hyperbolic random graphs. A hyperbolic random graph is a mathematical model for analyzing scale-free networks since it effectively explains the power-law degree distribution of scale-free networks. We propose a simple algorithm for finding a maximum clique in hyperbolic random graph. We first analyze the running time of our algorithm theoretically. We can compute a maximum clique on a hyperbolic random graph $G$ in $O(m + n^{4.5(1-α)})$ expected time if a geometric representation is given or in $O(m + n^{6(1-α)})$ expected time if a geometric representation is not given, where $n$ and $m$ denote the numbers of vertices and edges of $G$, respectively, and $α$ denotes a parameter controlling the power-law exponent of the degree distribution of $G$. Also, we implemented and evaluated our algorithm empirically. Our algorithm outperforms the previous algorithm [BFK18] practically and theoretically. Beyond the hyperbolic random graphs, we have experiment on real-world networks. For most of instances, we get large cliques close to the optimum solutions efficiently.

In this paper, we study the Planar Disjoint Paths problem: Given an undirected planar graph G with n vertices and a set T of k pairs (si, ti)ki=1 of vertices, the goal is to find a set P of k pairwise vertex-disjoint paths connecting si and ti for all indices i ∈ {1,…, k}. We present a 2O(k2)n-time algorithm for the Planar Disjoint Paths problem. This improves the two previously best-known algorithms: 22O(k)-time algorithm [Discrete Applied Mathematics 1995] and 2O(k2)n6-time algorithm [STOC 2020]. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.03341 † This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.2020R1C1C1012742).

In this paper, we present a linear-time approximation scheme for k -means clustering of incomplete data points in d -dimensional Euclidean space . An incomplete data point with Δ > 0 unspecified entries is represented as an axis-parallel affine subspace of dimension Δ. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for k -means clustering of n axis-parallel affine subspaces of dimension Δ that yields an ( 1 + ϵ ) -approximate solution in O ( n d ) time. The constants hidden behind O ( ⋅ ) depend only on Δ , ϵ and k . This improves the O ( n 2 d ) -time algorithm by Eiben et al. (2021) [7] by a factor of n .

In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size $k$, if it exists, which runs in time $2^{O(\sqrt{k})}(n+m)$, where $n$ and $m$ denote the numbers of vertices and edges, respectively. This improves the $2^{O(\sqrt{k}\log k)}n^{O(1)}$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Also, our algorithm can be extended to handle geometric intersection graphs of similarly sized fat objects without increasing the running time.

In this paper, we present a linear-time approximation scheme for $k$-means clustering of \emph{incomplete} data points in $d$-dimensional Euclidean space. An \emph{incomplete} data point with $Δ>0$ unspecified entries is represented as an axis-parallel affine subspaces of dimension $Δ$. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for $k$-means clustering of axis-parallel affine subspaces of dimension $Δ$ that yields an $(1+ε)$-approximate solution in $O(nd)$ time. The constants hidden behind $O(\cdot)$ depend only on $Δ, ε$ and $k$. This improves the $O(n^2 d)$-time algorithm by Eiben et al.[SODA'21] by a factor of $n$.

A Euclidean t-spanner for a point set V ⊂ ℝ^d is a graph such that, for any two points p and q in V, the distance between p and q in the graph is at most t times the Euclidean distance between p and q. Gudmundsson et al. [TALG 2008] presented a data structure for answering ε-approximate distance queries in a Euclidean spanner in constant time, but it seems unlikely that one can report the path itself using this data structure. In this paper, we present a data structure of size O(nlog n) that answers ε-approximate shortest-path queries in time linear in the size of the output.

Given a set of sites in a simple polygon, a geodesic Voronoi diagram of the sites partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n -gon, which improve the best known ones for \(m \le n/{\text {polylog}}n\) . Moreover, the algorithms for the geodesic nearest-point and farthest-point Voronoi diagrams are optimal for \(m \le n/{\text {polylog}}n\) . This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.

Given a set of m point sites in a simple polygon, the geodesic nearest-point Voronoi diagram of the sites partitions the polygon into m Voronoi cells, one cell per site, such that every point in a cell has the same nearest site under the geodesic metric. In this paper, we present an O(n + m log m)-time algorithm for computing the geodesic nearest-point Voronoi diagram of m points in a simple n-gon. This matches the best known lower bound of Ω(n + m log m) as well as improving the previously best known algorithms which take time O(n + m log m + m log2 n) and O(n log n + m log m). This answers the longstanding question whether the geodesic nearest-point Voronoi diagram can be computed optimally, which was explicitly posed by Aronov [Algorithmica, 1989] and Mitchell [Handbook of Computational Geometry, 2000].

Given a read-only memory for input and a write-only stream for output, an s-workspace algorithm, for a positive integer parameter s, is an algorithm using only O(s) words of workspace in addition to the memory for the input. In this paper, we present an $$O(n^2/s)$$ -time s-workspace algorithm for subdividing a simple n-gon into $$O(\min \{n/s,s\})$$ subpolygons of complexity $$O(\max \{n/s,s\})$$ . As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately by adopting the proposed subdivision: (1) computing the shortest path between two points inside a simple n-gon, (2) computing the shortest-path tree from a point inside a simple n-gon, (3) computing a triangulation of a simple n-gon. In addition, we improve the algorithm for problem (2) further by applying different approaches depending on the size of the workspace.

Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of n disks in the plane. Initially, all disks have radius 0, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is O ( n ( log ⁡ n + min ⁡ { log ⁡ Δ , log ⁡ Φ } ) ) , where Δ is the ratio of the fastest and the slowest growth rate and Φ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017]. Finally, we give an Ω ( n log ⁡ n ) lower bound, showing that our quadtree algorithms are almost tight.

We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance they travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log2⁡n) time for any two query positions s,t where the two persons start.

Given a set P of n points in the plane and a multiset W of k weights with k leq n, we assign a weight in W to a point in P to minimize the maximum weighted distance from the weighted center of P to any point in P. In this paper, we give two algorithms which take O(k^2 n^2 log^4 n) time and O(k^5 n log^4 k + kn log^3 n) time, respectively. For a constant k, the second algorithm takes only O(n log^3 n) time, which is near-linear.

We consider the following problem: Preprocess a set S of n axis-parallel boxes in Rd so that given a query with an axis-parallel box in Rd, the pairs of boxes of S whose intersection intersects the query box can be reported efficiently. For the case that d=2, we present a data structure of size O(nlog⁡n) supporting O(log⁡n+k) query time, where k is the size of the output. This improves the previously best known result by de Berg et al. which requires O(log⁡n+klog⁡n) query time using O(nlog⁡n) space. There has been no result known for this problem for higher dimensions, except that for d=3, the best known data structure supports O(nlog2⁡n+klog2⁡n) query time using O(nnlog⁡n) space. For a fixed dimension d>2, we present a data structure supporting O(n1−δlogd−1⁡n+klogd−1⁡n) query time for any constant 0<δ<1. The size of the data structure is O(nδd−2δ+1log⁡n).

We study the approximate range searching for three variants of the clustering problem with a set $P$ of $n$ points in $d$-dimensional Euclidean space and axis-parallel rectangular range queries: the $k$-median, $k$-means, and $k$-center range-clustering query problems. We present data structures and query algorithms that compute $(1+\varepsilon)$-approximations to the optimal clusterings of $P\cap Q$ efficiently for a query consisting of an orthogonal range $Q$, an integer $k$, and a value $\varepsilon>0$.

We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. Precisely, the amortized update time is O(sqrt{n}log n(log log n)^{3/2}) and the query time is O(log n(log log n)^2), where n is the number of edges in the subdivision. This answers a question posed by Snoeyink in the Handbook of Computational Geometry. When only deletions of edges are allowed, the update time and query time are just O(alpha(n)) and O(log n), respectively.

We study the point location problem in incremental (possibly disconnected) planar subdivisions, that is, dynamic subdivisions allowing insertions of edges and vertices only. Specifically, we present an O(n log n)-space data structure for this problem that supports queries in O(log^2 n) time and updates in O(log n log log n) amortized time. This is the first result that achieves polylogarithmic query and update times simultaneously in incremental planar subdivisions. Its update time is significantly faster than the update time of the best known data structure for fully-dynamic (possibly disconnected) planar subdivisions.

In this paper, we consider the quickest pair-visibility problem in polygonal domains. Given two points in a polygonal domain with h holes of total complexity n, we want to minimize the maximum distance that the two points travel in order to see each other in the polygonal domain. We present an O(n log^2 n+h^2 log^4 h)-time algorithm for this problem. We show that this running time is almost optimal unless the 3sum problem can be solved in O(n^{2-epsilon}) time for some epsilon>0.

We consider the geodesic convex hulls of points in a simple polygonal region in the presence of non-crossing line segments (barriers) that subdivide the region into simply connected faces. We present an algorithm together with data structures for maintaining the geodesic convex hull of points in each face in a sublinear update time under the fully-dynamic setting where both input points and barriers change by insertions and deletions. The algorithm processes a mixed update sequence of insertions and deletions of points and barriers. Each update takes O(n^2/3 log^2 n) time with high probability, where n is the total number of the points and barriers at the moment. Our data structures support basic queries on the geodesic convex hull, each of which takes O(polylog n) time. In addition, we present an algorithm together with data structures for geodesic triangle counting queries under the fully-dynamic setting. With high probability, each update takes O(n^2/3 log n) time, and each query takes O(n^2/3 log n) time.

Motivated by map labeling, we study the problem in which we are given a collection of n disks in the plane that grow at possibly different speeds. Whenever two disks meet, the one with the higher index disappears. This problem was introduced by Funke, Krumpe, and Storandt[IWOCA 2016]. We provide the first general subquadratic algorithm for computing the times and the order of disappearance. Our algorithm also works for other shapes (such as rectangles) and in any fixed dimension. Using quadtrees, we provide an alternative algorithm that runs in near linear time, although this second algorithm has a logarithmic dependence on either the ratio of the fastest speed to the slowest speed of disks or the spread of the disk centers (the ratio of the maximum to the minimum distance between them). Our result improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EWCG 2017]. Finally, we give an \Omega(n\log n) lower bound on the problem, showing that our quadtree algorithms are almost tight.

Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon.

We consider the problem of finding a shortcut connecting two vertices of a graph that minimizes the diameter of the resulting graph. We present an O(n^2 log^3 n)-time algorithm using linear space for the case that the input graph is a tree consisting of n vertices. Additionally, we present an O(n^2 log^3 n)-time algorithm using linear space for a continuous version of this problem.

Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an O(n log n)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.