The union volume estimation problem asks to (1±ε)-approximate the volume of the union of n given objects X₁,…,X_n ⊂ ℝ^d. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time O(n/ε²) in an oracle model where each object X_i can be accessed via three types of queries: obtain the volume of X_i, sample a random point from X_i, and test whether X_i contains a given point x. This running time was recently shown to be optimal [Bringmann, Larsen, Nusser, Rotenberg, and Wang, SoCG'25]. In another line of work, Meel, Vinodchandran, and Chakraborty [PODS'21] designed algorithms that read the objects in one pass using polylogarithmic time per object and polylogarithmic space; this can be phrased as a dynamic algorithm supporting insertions of objects for union volume estimation in the oracle model. In this paper, we study algorithms for union volume estimation in the oracle model that support both insertions and deletions of objects. We obtain the following results: 1) an algorithm supporting insertions and deletions in polylogarithmic update and query time and linear space (this is the first such dynamic algorithm, even for 2D triangles); 2) an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; 3) an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space.

A t-spanner of a point set X in a metric space (𝒳, δ) is a graph G with vertex set P such that, for any pair of points u,v ∈ 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 ε > 0, we maintain a (1+ε)-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 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.

In the online hitting set problem, sets arrive over time, and the algorithm has to maintain a subset of elements that hit all the sets seen so far. Alon, Awerbuch, Azar, Buchbinder, and Naor (SICOMP 2009) gave an algorithm with competitive ratio O(log n log m) for the (general) online hitting set and set cover problems for m sets and n elements; this is known to be tight for efficient online algorithms. Given this barrier for general set systems, we ask: can we break this double-logarithmic phenomenon for online hitting set/set cover on structured and geometric set systems? We provide an O(log n log log n)-competitive algorithm for the weighted online hitting set problem on set systems with linear shallow-cell complexity, replacing the double-logarithmic factor in the general result by effectively a single logarithmic term. As a consequence of our results we obtain the first bounds for weighted online hitting set for natural geometric set families, thereby answering open questions regarding the gap between general and geometric weighted online hitting set problems.

A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.

Oriented spanners were presented at ESA'23 as an extension of the well-researched geometric spanners: Given a set P of points in a metric space and an oriented graph G, the oriented dilation of two points p,q ∈ P is the length of the shortest closed walk in G containing p and q divided by the minimum perimeter triangle of p and q. G is called a t-spanner, if the maximum dilation over all pairs of points in P is at most t. This paper presents the first constructions of sparse oriented spanners for metric spaces beyond the Euclidean space. Given an orientation of the complete graph (i.e. a tournament) with dilation t on n points that satisfies an additional short-cycle property, we show how to extract a (t+ε)-spanner with 𝒪(k) edges in 𝒪(kn²+T(n)) time, for any metric space admitting a well-separated pair decomposition with k pairs computable in T(n) time. We supplement this with an improved construction of tournaments for metric point sets, obtaining dilation 5/3. This improves the previous bound of 2 and approaches the lower bound of 1.5. Combined, for n points in a metric space with constant doubling dimension d, this yields a (5/3 + ε)-spanner with (1/ε)^{𝒪(d)}n edges computable in (1/ε)^𝒪(d) n³ time using 𝒪(n²) space. This improves the dilation over the (2+ε)-spanner for Euclidean point sets presented at SoCG’25 while applying to more general metric spaces. Moreover, we generalize the known (2+ε)-spanner to doubling spaces. In particular, an oriented (2+ε)-spanner with 𝒪(ε^{-d} n) edges can be constructed in (1/ε)^𝒪(d) n log n time using 𝒪(ε^{-d} n) space. Since the oriented dilation can be dominated by one pair of points, we also consider the oriented average dilation, which is the sum over the oriented dilation of all pairs of points divided by the number of pairs. While oriented (1+ε)-spanners do not exist for every point set, we present an algorithm that computes a spanner with average dilation 1+ε for point sets in a metric space of constant doubling dimension d: More concretely, our algorithm computes an oriented spanner with average dilation at most 1 + 𝒪(1/s) + s^𝒪(d)/n with s^𝒪(d) n edges in s^𝒪(d) n log n time using s^𝒪(d) n space, where s is any sufficiently large number that may depend on n.

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.

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 two fundamental geometric problems on a dynamic set of n axis-parallel boxes in d-dimensional space. The maximum depth problem asks for the largest number of boxes that contain a common point, whereas Klee’s measure problem asks for the volume of the union of the boxes. We present fully dynamic exact data structures for both problems achieving Õ(n^{(d-1)/2}) amortized update time. This update time is optimal for an exact dynamic algorithm, up to logarithmic factors, assuming the Combinatorial k-Clique Hypothesis. Previously, matching bounds were established only for d = 1 [Imai and Asano, J. Algo.'83], and for d = 2 [Suri, Xue, Yang, and Zhu, SoCG'25]. Our approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell. This argument allows us to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates. We believe this technique may be of independent interest for other dynamic geometric problems.

Given two polygons of complexities \(n\) and \(m\) respectively, a fundamental problem in shape matching and geometric similarity is to compute their maximum area overlap under translation. For general simple polygons, the best-known algorithm runs in \(\mathcal{O}((nm)^2 \log(nm))\) time [Mount, Silverman, Wu ’96]. In a recent breakthrough that received the SoCG Best Paper Award 2025, Chan and Hair gave a linear-time algorithm for the special case when both polygons are convex. A key challenge in computational geometry is to design improved algorithms for other natural classes of polygons. We address this by presenting an \(\mathcal{O}((nm)^{3/2} \log(nm))\)-time algorithm for the case when both polygons are orthogonal, probably the most popular class of polygons besides convex and simple ones. This is the first algorithm for polygon overlap on orthogonal polygons that is faster than the almost 30 years old algorithm for general simple polygons.

Abstract A fundamental question is whether one can maintain a maximum independent set in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. Already, for a set of intervals, it is known that no dynamic algorithm can maintain an exact maximum independent set in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate maximum independent set in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n disks of unit radius in the plane, we show that a 12-approximate maximum independent set can be maintained with worst-case update time $$O(\log n)$$ O ( log n ) , and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d , where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain $$O(1+\varepsilon )$$ O ( 1 + ε ) -approximate maximum independent set in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (2021) that can smoothly transition from one independent set to another; hence it suffices to maintain a family of independent sets where the largest one is a constant-factor approximation of a maximum independent set. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (2020) and Liu (2022), which generalizes the dynamic convex hull data structure by Chan (2010), and allows us to quickly find a “replacement” disk (if any) when a disk in one of our independent sets is deleted.

VC-dimension (Vapnik & Chervonenkis (1971)) and $\varepsilon$-nets (Haussler & Welzl (1987)) are key concepts in Statistical Learning Theory. Intuitively, VC-dimension is a measure of the size of a class of sets. The famous $\varepsilon$-net theorem, a fundamental result in Discrete Geometry, asserts that if the VC-dimension of a set system is bounded, then a small sample exists that intersects all sufficiently large sets. In online learning scenarios where data arrives sequentially, the VC-dimension helps to bound the complexity of the set system, and $\varepsilon$-nets ensure the selection of a small representative set. This sampling framework is crucial in various domains, including spatial data analysis, motion planning in dynamic environments, optimization of sensor networks, and feature extraction in computer vision, among others. Motivated by these applications, we study the online $\varepsilon$-net problem for geometric concepts with bounded VC-dimension. While the offline version of this problem has been extensively studied, surprisingly, there are no known theoretical results for the online version to date. We present the first deterministic online algorithm with an optimal competitive ratio for intervals in $\mathbb{R}$. Next, we give a randomized online algorithm with a near-optimal competitive ratio for axis-aligned boxes in $\mathbb{R}^d$, for $d\le 3$. Furthermore, we introduce a novel technique to analyze similar-sized objects of constant description complexity in $\mathbb{R}^d$, which may be of independent interest. Next, we focus on the continuous version of this problem (called online piercing set), where ranges of the set system are geometric concepts in $\mathbb{R}^d$ arriving in an online manner, but the universe is the entire ambient space, and the objective is to choose a small sample that intersects all the ranges. Although online piercing set is a very well-studied problem in the literature, to our surprise, very few works have addressed generic geometric concepts without any assumption about the sizes. We advance this field by proposing asymptotically optimal competitive deterministic algorithms for boxes and ellipsoids in $\mathbb{R}^d$, for any $d\in\mathbb{N}$.

We develop simple and general techniques to obtain faster (near-linear time) static approximation algorithms, as well as efficient dynamic data structures, for four fundamental geometric optimization problems: minimum piercing set (MPS), maximum independent set (MIS), minimum vertex cover (MVC), and maximum-cardinality matching (MCM). Highlights of our results include the following:

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant ε ∈ (0,1), one could construct a (2 + ε )-spanner with O (n log(n )) edges (SICOMP 2019), and there is a lower bound of Ω(n2) edges for any (2 — ε )-spanner (SoCG 2015). The main open question is whether a linear number of edges suffices and the stretch can be reduced to 2. We resolve this problem by showing that for stretch 2, one needs Ω(n log n ) edges, and for stretch 2 + ε for any fixed ε ∈ (0,1), O (n ) edges are sufficient. Our lower bound is the first super-linear lower bound for stretch 2.

In this article, we study the online Euclidean spanners problem for points in \(\mathbb{R}^{d}\) . Given a set \(S\) of \(n\) points in \(\mathbb{R}^{d}\) , a \(t\) -spanner on \(S\) is a subgraph of the underlying complete graph \(G=(S,\binom{S}{2})\) , that preserves the pairwise Euclidean distances between points in \(S\) to within a factor of \(t\) , that is the stretch factor . Suppose we are given a sequence of \(n\) points \((s_{1},s_{2},\ldots,s_{n})\) in \(\mathbb{R}^{d}\) , where point \(s_{i}\) is presented in step \(i\) for \(i=1,\ldots,n\) . The objective of an online algorithm is to maintain a geometric \(t\) -spanner on \(S_{i}=\{s_{1},\ldots,s_{i}\}\) for each step \(i\) . The algorithm is allowed to add new edges to the spanner when a new point is presented but cannot remove any edge from the spanner. The performance of an online algorithm is measured by its competitive ratio, which is the supremum, over all sequences of points, of the ratio between the weight of the spanner constructed by the algorithm and the weight of an optimum spanner. Here, the weight of a spanner is the sum of all edge weights. First, we establish a lower bound of \(\Omega(\varepsilon^{-1}\log n/\log\varepsilon^{-1})\) for the competitive ratio of any online \((1+\varepsilon)\) -spanner algorithm, for a sequence of \(n\) points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a \((1+\varepsilon)\) -spanner with competitive ratio \(O(\varepsilon^{-1}\log n/\log\varepsilon^{-1})\) . Next, we design online algorithms for sequences of points in \(\mathbb{R}^{d}\) , for any constant \(d\geq 2\) , under the \(L_{2}\) norm. We show that previously known incremental algorithms achieve a competitive ratio \(O(\varepsilon^{-(d+1)}\log n)\) . However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of \(\varepsilon\) . We describe an online Steiner \((1+\varepsilon)\) -spanner algorithm with competitive ratio \(O(\varepsilon^{(1-d)/2}\log n)\) . As a counterpart, we show that the dependence on \(n\) cannot be eliminated in dimensions \(d\geq 2\) . In particular, we prove that any online spanner algorithm for a sequence of \(n\) points in \(\mathbb{R}^{d}\) under the \(L_{2}\) norm has competitive ratio \(\Omega(f(n))\) , where \(\lim_{n\rightarrow\infty}f(n)=\infty\) . Finally, we provide improved lower bounds under the \(L_{1}\) norm: \(\Omega(\varepsilon^{-2}/\log\varepsilon^{-1})\) in

A fundamental question is whether one can maintain a maximum independent set (MIS) in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. For a set of intervals, it is known that no dynamic algorithm can maintain an exact MIS in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate MIS in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n unit disks in the plane, we show that a 12-approximate MIS can be maintained with worst-case update time O(log n), and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d, where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain O(1+ε)-approximate MIS in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (ESA 2021) that can smoothly transition from one independent set to another; hence it suffices to maintain a family of independent sets where the largest one is an O(1)-approximate MIS. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (DCG 2020) and Liu (SICOMP 2022), which generalizes the dynamic convex hull data structure by Chan (JACM 2010), and quickly yields a "replacement" disk (if any) when a disk in one of our independent sets is deleted.

We study the geometric knapsack problem in which we are given a set of $d$-dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that can be packed non-overlappingly into a given $d$-dimensional (unit hypercube) knapsack. Even if $d=2$ and all input objects are disks, this problem is known to be \textsf{NP}-hard [Demaine, Fekete, Lang, 2010]. In this paper, we give polynomial time $(1+\varepsilon)$-approximation algorithms for the following types of input objects in any constant dimension $d$: - disks and hyperspheres, - a class of fat convex polygons that generalizes regular $k$-gons for $k\ge 5$ (formally, polygons with a constant number of edges, whose lengths are in a bounded range, and in which each angle is strictly larger than $π/2$), - arbitrary fat convex objects that are sufficiently small compared to the knapsack. We remark that in our \textsf{PTAS} for disks and hyperspheres, we output the computed set of objects, but for a $O_\varepsilon(1)$ of them, we determine their coordinates only up to an exponentially small error. However, it is unclear whether there always exists a $(1+\varepsilon)$-approximate solution that uses only rational coordinates for the disks' centers. We leave this as an open problem that is related to well-studied geometric questions in the realm of circle packing.

Low-distortional metric embeddings are a crucial component in the modern algorithmic toolkit. In an online metric embedding, points arrive sequentially and the goal is to embed them into a simple space irrevocably, while minimizing the distortion. Our first result is a deterministic online embedding of a general metric into Euclidean space with distortion if the metric has doubling dimension d), solving affirmatively a conjecture by Newman and Rabinovich (2020), and quadratically improving the dependence on the aspect ratio Φ from Indyk et al. (2010). Our second result is a stochastic embedding of a metric space into trees with expected distortion O(d·log Φ), generalizing previous results (Indyk et al. (2010), Bartal et al. (2020)).

Abstract. Given a metric space [Formula: see text], a weighted graph [Formula: see text] over [Formula: see text] is a metric [Formula: see text]-spanner of [Formula: see text] if for every [Formula: see text], [Formula: see text], where [Formula: see text] is the shortest path metric in [Formula: see text]. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points [Formula: see text], where the points are presented one at a time (i.e., after [Formula: see text] steps, we see [Formula: see text]). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a [Formula: see text]-spanner [Formula: see text] for [Formula: see text] for all [Formula: see text], while minimizing the number of edges, and their total weight. We construct online [Formula: see text]-spanners in the Euclidean [Formula: see text]-space, [Formula: see text]-spanners for general metrics, and [Formula: see text]-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a [Formula: see text]-spanner with competitive ratio [Formula: see text], bypassing the classic lower bound [Formula: see text] for lightness, which compares the weight of the spanner to that of the minimum spanning tree.

The task of finding an extension to a given partial drawing of a graph while adhering to constraints on the representation has been extensively studied in the literature, with well-known results providing efficient algorithms for fundamental representations such as planar and beyond-planar topological drawings. In this paper, we consider the extension problem for bend-minimal orthogonal drawings of planar graphs, which is among the most fundamental geometric graph drawing representations. While the problem was known to be NP-hard, it is natural to consider the case where only a small part of the graph is still to be drawn. Here, we establish the fixed-parameter tractability of the problem when parameterized by the size of the missing subgraph. Our algorithm is based on multiple novel ingredients which intertwine geometric and combinatorial arguments. These include the identification of a new graph representation of bend-equivalent regions for vertex placement in the plane, establishing a bound on the treewidth of this auxiliary graph, and a global point-grid that allows us to discretize the possible placement of bends and vertices into locally bounded subgrids for each of the above regions.

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G=(V,E) into a planar straight-line circular drawing of G by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is obvious that such a crossing-free circular drawing always exists and we define the circular shifting number shift∘(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift∘(δG)≤K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift∘(δG)≤n−⌊n−2⌋−2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all of the crossings. For this problem, we provide a tight upper bound shift∘(δG)≤⌊n2⌋−1 and present an O(n2)-time algorithm to compute the circular shifting number of almost-planar drawings.

We study a variant of the geometric multicut problem, where we are given a set $\mathcal{P}$ of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where $\mathcal{P}$ contains a polygon $Q$ that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an $O(n \log n)$-time algorithm for the case that the convex hull of $\mathcal{P} \setminus \{Q\}$ does not intersect $Q$.

Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits a $(1+\varepsilon)$-spanner with $O(n)$ edges and weight proportional to that of the Euclidean minimum spanning tree of $S$. In a recent breakthrough, Le and Solomon [Proceedings of FOCS, 2019, pp. 1078--1100] established the precise dependencies on $\varepsilon>0$, for constant $d\in \mathbb{N}$, of the minimum lightness and sparsity of $(1+\varepsilon)$-spanners, and observed that Steiner points can substantially improve the lightness and sparsity of a $(1+\varepsilon)$-spanner. They gave upper bounds of $\tilde{O}(\varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $d\geq 3$ and $\tilde{O}(\varepsilon^{-(d-1)/2})$ for the minimum sparsity in $d$-space for all $d\geq 1$. Subsequently, Le and Solomon [ LIPIcs Leibniz Int. Proc. Inform. 173, Schloss Dagstuhl, Wadern, 2020, pp. 67:1--67:22] constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\log\Delta)$ in the plane, where $\Delta\in \Omega(\sqrt{n})$ is the spread of $S$, defined as the ratio between the maximum and the minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner $(1+\varepsilon)$-spanners. We establish lower bounds of $\Omega(\varepsilon^{-d/2})$ for the lightness and $\Omega(\varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all constant $d\geq 2$. Our lower bound constructions generalize previous constructions by Le and Solomon, but the analysis substantially simplifies previous work, using new geometric insight, focusing on the directions of edges. Next, we show that for every finite set of points in the plane and every $\varepsilon\in (0,1]$, there exists a Euclidean Steiner $(1+\varepsilon)$-spanner of lightness $O(\varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.

Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in $\mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on $\varepsilon>0$ and $d\in \mathbb{N}$ of the minimum lightness of $(1+\varepsilon)$-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\logΔ)$ in the plane, where $Δ\geq Ω(\sqrt{n})$ is the \emph{spread} of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness $\tilde{O}(\varepsilon^{-(d+1)/2})$ in dimensions $d\geq 3$. Recently, Bhore and Tóth (2020) established a lower bound of $Ω(\varepsilon^{-d/2})$ for the lightness of Steiner $(1+\varepsilon)$-spanners in $\mathbb{R}^d$, for $d\ge 2$. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions $d\geq 2$. In this work, we show that for every finite set of points in the plane and every $\varepsilon>0$, there exists a Euclidean Steiner $(1+\varepsilon)$-spanner of lightness $O(\varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016).

The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and $O(m^{1/2}\log n)$ space, where $n$ is the number of Jordan regions, and $m$ is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial-time and $O(m^{1/2}\log n)$ space algorithm, where $n$ and $m$ are the number of vertices and edges, respectively. However, we use a more involved technique for unit contact disk graphs (penny graphs) and obtain a better algorithm. We show that for every $ε> 0$, there exists a polynomial-time algorithm that can solve Reachability in an $n$ vertex directed penny graph, using $O(n^{1/4+ε})$ space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.

Lightness and sparsity are two natural parameters for Euclidean (1+ε)-spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in d-space admits an (1+ε)-spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)-spanner. They gave upper bounds of Õ(ε^{-(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{-(d-1))/2}) for the minimum sparsity in d-space for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)-spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{-d/2}) for the lightness and Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)-spanners of lightness O(ε^{-1}log n) for n points in Euclidean plane.

A $k$-page book embedding of a graph $G$ draws the vertices of $G$ on a line and the edges on $k$ half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether $G$ admits a $k$-page book embedding both when the linear order of the vertices is fixed, called ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$, or not fixed, called ${\rm B{\small OOK}~T{\small HICKNESS}}$. Both problems are known to be ${\sf NP}$-complete in general. We show that ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ and ${\rm B{\small OOK}~T{\small HICKNESS}}$ are fixed-parameter tractable parameterized by the vertex cover number of the graph and that ${\rm F{\small IXED}-O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ is fixed-parameter tractable parameterized by the pathwidth of the vertex order.