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.

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an $(α, β)$-SLT of $G$ w.r.t. $s \in V$ is a spanning tree of $G$ with root-stretch $α$ (preserving all distances between $s$ and the other vertices up to a factor of $α$) and lightness $β$ (its weight is at most $β$ times the weight of a minimum spanning tree of $G$). Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards this question by presenting two bicriteria approximation algorithms. For any $ε>0$, a set $P$ of $n$ points in constant-dimensional Euclidean space and a source $s\in P$, our first (respectively, second) algorithm returns, in $O(n \log n \cdot {\rm polylog}(1/ε))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(ε\log ε^{-1})$ and weight at most $O(\mathrm{opt}_ε\cdot \log^2 ε^{-1})$ (resp., $O(\mathrm{opt}_ε\cdot \log ε^{-1})$), where $\mathrm{opt}_ε$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+ε$.

We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.

In their seminal paper, Althöfer et al. (DCG 1993) introduced the greedy spanner and showed that, for any weighted planar graph \(G\), the weight of the greedy \((1+\epsilon)\)-spanner is at most \((1+\tfrac{2}{\epsilon})\cdot \textrm w(\mathsf{MST}(G))\), where \(\textrm w(\mathsf{MST}(G))\) is the weight of a minimum spanning tree \(\mathrm{MST}(G)\) of \(G\). This bound is optimal in an \(\textcolor{#ff6666}{existential\ sense}\): there exist planar graphs \(G\) for which any \((1+\epsilon)\)-spanner has a weight of at least \((1+\tfrac{2}{\epsilon})\cdot w(\mathrm{MST}(G))\).

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.

We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be to ensure the existence of n points that are the vertices of a convex n-gon. Moreover, Erdős further extended this problem by asking what happens if we also require that this n-gon has an empty interior. In a 2-player Maker-Breaker setting, this problem inspires two main games. In both games, Maker tries to obtain an empty convex k-gon, while Breaker tries to prevent her from doing so. The games differ only in which points can comprise the winning k-gons: in the monochromatic version the points of both players can make up a k-gon, while in the bichromatic version only Maker’s points contribute to such a polygon. Both settings are studied in this paper. We show that in the monochromatic game, Maker always wins. Even in a biased game where Breaker is allowed to place s points per round, for any constant $$s \ge 1$$ , Maker has a winning strategy. In the bichromatic setting, Maker still wins whenever Breaker is allowed to place s points per round for any constant $$s<2$$ . This settles an open problem posed in 2019. Furthermore, we show that there are games that are not a lost cause for Breaker. Whenever $$k\ge 8$$ and Breaker is allowed to play 12 or more points per round, she has a winning strategy. We also consider the one-round bichromatic game (a.k.a. the offline version). In this setting, we show that Breaker wins if she can place twice as many points as Maker but if the bias is less than 2, then Maker wins for large enough set of points.

Publisher Copyright: © Minati De, Satyam Singh, and Csaba D. Tóth;

Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.

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.

Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known.

For a set of red and blue points in the plane, a Minimum Bichromatic Spanning Tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in \(O(n\log n)\) time where \( n \) is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a Minimum Plane Bichromatic Spanning Tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al., has a ratio of \(O(\sqrt{n})\) . It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an \(O(\log n)\) -factor approximation algorithm for the general case.

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.

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner$E$12We shall identify a graph$H = (X,E)$with its edge set$E$. All edge weights are given by the Euclidean distances. are the size (number of edges)$\vert E\vert$and the weight (sum of edge weights)$\Vert E\Vert$. The state-of-the-art constructions of Euclidean$(1+\epsilon)$-spanners in$\mathbb{R}^{d}$have$o_{d}(_{n\cdot\epsilon^{-d+1}})$edges (or sparsity$O_{d}(\epsilon^{-d+1}))$and weight$O_{d}(\epsilon^{-d} \log \epsilon^{-1}) \cdot\Vert E_{\text{mst}}\Vert$(or lightness$O_{d}(\epsilon^{-d}\log\epsilon^{-1}))$; here$O_{d}$suppresses a factor of$d^{O(d)}$and$\Vert E_{\text{mst}}\Vert$denotes the weight of a minimum spanning tree of the input point set. Importantly, these two upper bounds are (near-)optimal (up to the$d^{O(d)}$factor and disregarding the factor of$\log(\epsilon^{-1})$in the lightness bound) for some extremal instances [Le and Solomon, 2019], and therefore they are (near-)optimal in an existential sense. Moreover, both these upper bounds are attained by the same construction-the classic greedy spanner, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for any point set instance? Motivated by this question, we initiate the study of instance optimal Euclidean spanners. Our results are two-fold. •Rather surprisingly (given the aforementioned experimental study), we demonstrate that the greedy spanner is far from being instance optimal, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy$(1+x\epsilon)$-spanner (for basically any parameter$x \geq 1$) has$\Omega_{x}(\epsilon^{-1/2})\cdot\vert E_{\text{spa}} \vert$edges and weight$\Omega_{x}(\epsilon^{-1})\cdot\Vert E_{\text{light}}\Vert$, where$E_{\text{spa}}$and$E_{\text{light}}$denote the per-instance sparsest and lightest$(1 +\epsilon)$-spanners, respectively, and the$\Omega_{x}$notation suppresses a polynomial dependence on$1/x$. •As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of$1+\epsilon\cdot 2^{O(\log^{*}(d/\epsilon)}$with$O(1)\cdot\vert E_{\text{spa}}\vert$edges and weight$O(1)$. $\Vert E_{ \text{light}}\Vert$. In other words, we show that a slight increase to the stretch suffices for obtaining instance optimality up to an absolute constant for both sparsity and lightness. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer$k\geq 1$, we can construct a Euclidean spanner in$\mathbb{R}^{d}$of stretch$1+\epsilon\cdot 2^{O(k)}$with$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\vert E_{\text{spa}}\vert$edges and weight$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\Vert E_{\text{light}}\Vert$, where$\log^{(k)}$denotes the k-iterated logarithm.

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.

We introduce the Observation Route Problem ( ORP ) defined as follows: Given a set of n pairwise disjoint obstacles (regions) in the plane, find a shortest tour (route) such that an observer walking along this tour can see (observe) each obstacle from some point of the tour. The observer does not need to see the entire boundary of an obstacle. The tour is not allowed to intersect the interior of any region (i.e., the regions are obstacles and therefore out of bounds). The problem exhibits similarity to both the Traveling Salesman Problem with Neighborhoods ( TSPN ) and the External Watchman Route Problem ( EWRP ). We distinguish two variants: the range of visibility is either limited to a bounding rectangle, or unlimited. We obtain the following results: (I) Given a family of n disjoint convex bodies in the plane, computing a shortest observation route does not admit a ( c log ⁡ n ) -approximation unless P = NP for an absolute constant c > 0 . (This holds for both limited and unlimited vision.) (II) Given a family of disjoint convex bodies in the plane, computing a shortest external watchman route is NP -hard. (This holds for both limited and unlimited vision; and even for families of axis-aligned squares.) (III) Given a family of n disjoint fat convex polygons in the plane, an observation tour whose length is at most O ( log ⁡ n ) times the optimal can be computed in polynomial time. (This holds for limited vision.) (IV) For every n ≥ 5 , there exists a convex polygon with n sides and all angles obtuse such that its perimeter is not a shortest external watchman route. This refutes a conjecture by Absar and Whitesides (2006).

Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon $\mathcal{R}$, called a district map, is a set of interior disjoint connected polygons called districts whose union equals $\mathcal{R}$. We consider the recombination as the reconfiguration move which takes a subdivision and produces another by merging two adjacent districts, and by splitting them into two connected polygons of the same area as the original districts. The complexity of a map is the number of vertices in the boundaries of its districts. Given two maps with $k$ districts, with complexity $O(n)$, and a perfect matching between districts of the same area in the two maps, we show constructively that $(\log n)^{O(\log k)}$ recombination moves are sufficient to reconfigure one into the other. We also show that $Ω(\log n)$ recombination moves are sometimes necessary even when $k=3$, thus providing a tight bound when $k=O(1)$.

A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p,q∈P if and only if |pq|≤1. A spanning subgraph G′ of G is a k-hop spanner if and only if for every edge pq∈G, there is a path between p,q in G′ with at most k edges. We obtain the following results for unit disk graphs in the plane. Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. Every n-vertex unit disk graph has a 2-hop spanner with O(nlog⁡n) edges. This is the first nontrivial construction of 2-hop spanners. For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. For every finite point set on a circle, there exists a plane (i.e., crossing-free) 4-hop spanner. As such, this provides a tight bound for points on a circle. The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k.

We study the atomic embeddability testing problem, which is a common generalization of clustered planarity ( c-planarity , for short) and thickenability testing, and present a polynomial-time algorithm for this problem, thereby giving the first polynomial-time algorithm for c-planarity. C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin’s work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory. Finally, we give a polynomial-time reduction from atomic embeddability to thickenability thereby showing that both problems are polynomially equivalent, and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.

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.

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k,s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s, each of which induces a connected subgraph (when s=0, the k parts are perfectly balanced, and we call it k-BCP for short). A recombination is an operation that takes a (k,s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0, we wish to determine whether there exists a sequence of recombinations that transform A into B via (k,s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k, (3) there exist negative instances for s≤n/(3k), and (4) we show that determining whether a sequence of recombination that connects two (k,s)-BCP of a graph G exists is PSPACE-complete when k∈O(nε) and s∈O(n1−ε), for any constant 0<ε≤1. This statement holds even for restricted settings such as when G is an edge-maximal planar graph or when k≥3 and G is planar.

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.

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.

Let P be a set of n points in the plane, no three in a line. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the crossing type (for short, x-type) of P specifies, for every unordered pair of line segments spanned by P, whether they cross each other. Keller and Perles (2016) proved that the x-type of P can be reconstructed from the exchange graph G0(P) of noncrossing spanning trees. In this paper, we show that the x-type of P can already be reconstructed from the compatible exchange graph G1(P), which is a subgraph of G0(P). The proof crucially relies on the analysis of maximal sets of pairwise noncrossing edges (msnes) between two disjoint planar straight-line graphs. msnes are a bipartite analogue of triangulations of planar straight-line graphs; they correspond to maximal cliques in G1(P).

Let $P=(p_1, p_2, \dots, p_n)$ be a polygonal chain in $\mathbb{R}^d$. The stretch factor of $P$ is the ratio between the total length of $P$ and the distance of its endpoints, $\sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|$. For a parameter $c \geq 1$, we call $P$ a $c$-chain if $|p_ip_j|+|p_jp_k| \leq c|p_ip_k|$ for every triple $(i,j,k)$, $1 \leq i 0$, there is a noncrossing $c$-chain that has stretch factor $\Omega(n^{1/2-\varepsilon})$ for sufficiently large constant $c=c(\varepsilon)$; (ii) on the other hand, the stretch factor of a $c$-chain $P$ is $O(n^{1/2})$ for every constant $c\geq 1$, regardless of whether $P$ is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain $P$ in $\mathbb{R}^2$ with $n$ vertices, the minimum $c\geq 1$ for which $P$ is a $c$-chain in $O(n^{2.5}\ {\rm polylog}\ n)$ expected time and $O(n\log n)$ space. These results generalize to $\mathbb{R}^d$. For every dimension $d\geq 2$ and every $\varepsilon>0$, we construct a noncrossing $c$-chain that has stretch factor $\Omega(n^{(1-\varepsilon)(d-1)/d})$; on the other hand, the stretch factor of any $c$-chain is $O((n-1)^{(d-1)/d})$; for every $c>1$, we can test whether an $n$-vertex chain in $\mathbb{R}^d$ is a $c$-chain in $O(n^{3-1/d}\ {\rm polylog}\ n)$ expected time and $O(n\log n)$ space.

Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.

We construct a convex polytope of unit diameter that when placed on a horizontal surface on one of its faces, it repeatedly rolls over from one face to another until it comes to rest on some face, far away from its start position: that is, the horizontal distance between the footprints of the start and final faces can be larger than any given threshold. According to the laws of physics, the vertical distance between the center of mass of the polytope and the horizontal surface continuously decreases throughout the entire motion. The speed of the motion is irrelevant. Specifically, if the polytope is manually stopped after each tumble, the motion resumes when released (unless it stands on the final stable face). Moreover, such a polytope can be realized so that (i) it has a unique stable face, and (ii) it is an arbitrary close approximation of a unit ball. As such, this construction gives a positive answer to a question raised by Conway (1969). The arbitrarily large rolling distance property investigated here for the first time raises intriguing questions and opens new avenues for future research.

We study the atomic embeddability testing problem, which is a common generalization of clustered planarity (c-planarity, for short) and thickenability testing, and present a polynomial time algorithm for this problem, thereby giving the first polynomial time algorithm for c-planarity. C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently, despite relentless efforts. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin's work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory. Finally we give a polynomial-time reduction from c-planarity to thickenability and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.

Given a planar straight-line graph G=(V,E) in R^2, a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P. We prove that every arrangement of n disjoint line segments in the plane has a subset of size Omega(sqrt{n}) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R^3. We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization.

We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.

Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the total length of P and the distance of its endpoints, sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|. For a parameter c >= 1, we call P a c-chain if |p_ip_j|+|p_jp_k| <= c|p_ip_k|, for every triple (i,j,k), 1 <= i 0, there is a noncrossing c-chain that has stretch factor Omega(n^{1/2-epsilon}), for sufficiently large constant c=c(epsilon); (ii) on the other hand, the stretch factor of a c-chain P is O(n^{1/2}), for every constant c >= 1, regardless of whether P is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain P in R^2 with n vertices, the minimum c >= 1 for which P is a c-chain in O(n^{2.5} polylog n) expected time and O(n log n) space.

With the popularity of portable wireless devices it is important to model and predict how information or contagions spread by natural human mobility - for understanding the spreading of deadly infectious diseases and for improving delay tolerant communication schemes. Formally, we model this problem by considering M moving agents, where each agent initially carries a distinct bit of information. When two agents are at the same location or in close proximity to one another, they share all their information with each other. We would like to know the time it takes until all bits of information reach all agents, called the flood time, and how it depends on the way agents move, the size and shape of the network and the number of agents moving in the network.

Given a point set S={s_1,... , s_n} in the unit square U=[0,1]^2, an anchored square packing is a set of n interior-disjoint empty squares in U such that s_i is a corner of the ith square. The reach R(S) of S is the set of points that may be covered by such a packing, that is, the union of all empty squares anchored at points in S. It is shown that area(R(S))>= 1/2 for every finite set S subset U, and this bound is the best possible. The region R(S) can be computed in O(n log n) time. Finally, we prove that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a geometric packing problem where the size of geometric objects in the packing is unrestricted.

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding φ : G → M of a graph G into a 2-manifold M maps the vertices in V (G) to distinct points and the edges in E (G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map φ : G → M comes from an embedding. A map φ : G → M is a weak embedding if it can be perturbed into an embedding ψε : G → M with ║φ – ψε║ < ε for every ε > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl [14], which reduces to solving a system of linear equations over ℤ2. It runs in O(π2ω) ≤ O(n4.75) time, where ω ≈ 2.373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually “untangles” the image φ(G) into an embedding ψ(G), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.

It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross.

We study vertex-labeled graphs that can be embedded on a given point set such that every edge is a polyline with $k$ bends per edge, where $k\in \mathbb{N}$. It is shown that on every $n$-element point set in the plane, at most $\exp(O(n\log(2+k)))$ labeled graphs can be embedded using polyline edges with $k$ bends per edge, and this bound is the best possible. This is the first exponential upper bound for the number of labeled plane graphs where the edges are polylines of constant complexity. Standard tools developed for the enumeration of straight-line graphs, such as triangulations and crossing numbers, do not seem applicable in this scenario. Furthermore, the exponential upper bound does not carry over to other popular relaxations of straight-line edges; for example, the number of labeled planar graphs that admit an embedding with $x$-monotone edges on $n$ points is superexponential.

We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n^2 log n)-time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.

Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garcia et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.

Given n line segments in the plane, do they form the edge set of a weakly simple polygon; that is, can the segment endpoints be perturbed by at most epsilon, for any epsilon > 0, to obtain a simple polygon? While the analogous question for simple polygons can easily be answered in O(n log n) time, we show that it is NP-complete for weakly simple polygons. We give O(n)-time algorithms in two special cases: when all segments are collinear, or the segment endpoints are in general position. These results extend to the variant in which the segments are directed, and the counterclockwise traversal of a polygon should follow the orientation. We study related problems for the case that the union of the n input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems.

We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R d , for d ⩾ 3) or improvements over previous approximations achievable in comparable times (for unit disks in the plane). (I) Given a set of n hyperplanes in R d , a traveling salesman problem (TSP) tour whose length is at most O (1) times the optimal can be computed in O ( n ) time when d is constant. (II) Given a set of n lines in R d , a TSP tour whose length is at most O (log 3 n ) times the optimal can be computed in polynomial time for all d . (III) Given a set of n unit balls in R d , a TSP tour whose length is at most O (1) times the optimal can be computed in polynomial time when d is constant.

We show that every triangulation (maximal planar graph) on n\ge 6 vertices can be flipped into a Hamiltonian triangulation using a sequence of less than n/2 combinatorial edge flips. The previously best upper bound uses 4-connectivity as a means to establish Hamiltonicity. But in general about 3n/5 flips are necessary to reach a 4-connected triangulation. Our result improves the upper bound on the diameter of the flip graph of combinatorial triangulations on n vertices from 5.2n-33.6 to 5n-23. We also show that for every triangulation on n vertices there is a simultaneous flip of less than 2n/3 edges to a 4-connected triangulation. The bound on the number of edges is tight, up to an additive constant. As another application we show that every planar graph on n vertices admits an arc diagram with less than n/2 biarcs, that is, after subdividing less than n/2 (of potentially 3n-6) edges the resulting graph admits a 2-page book embedding.

The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given planar convex body was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the convex body. In 1991, Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex $n$-gon. He conjectured that the barrier found by his algorithm is optimal, but this was refuted recently by Provan et al. Here, we give a Shermer-like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in $O(n)$ time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.

The problem of finding a collection of curves of minimum total length that meet all the lines intersecting a given polygon was initiated by Mazurkiewicz in 1916. Such a collection forms an opaque barrier for the polygon. In 1991 Shermer proposed an exponential-time algorithm that computes an interior-restricted barrier made of segments for any given convex n-gon. He conjectured that the barrier found by his algorithm is optimal, however this was refuted recently by Provan et al. Here we give a Shermer like algorithm that computes an interior polygonal barrier whose length is at most 1.7168 times the optimal and that runs in O(n) time. As a byproduct, we also deduce upper and lower bounds on the approximation ratio of Shermer's algorithm.

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a planar straight-line embedding that realizes these lengths; and G is extrinsically free in H if all constraints on the edge lengths of G depend on G only, irrespective of additional edges of the host H.

It is shown that on every n-element point set in the plane, at most exp(O(kn)) labeled planar graphs can be embedded using polyline edges with k bends per edge. This is the first exponential upper bound for the number of labeled plane graphs where the edges are polylines of constant size. Several standard tools developed for the enumeration of straight-line graphs, such as triangulations and crossing numbers, are unavailable in this scenario. Furthermore, the exponential upper bound does not carry over to other popular relaxations of straight-line edges: for example, the number of plane graphs realizable with x-monotone edges on n points is already super-exponential.

For every $n\in \mathbb{N}$, we construct an $n$-vertex planar graph $G=(V,E)$ and $n$ distinct points $p(v)$, $v\in V$, in the plane such that in any crossing-free straight-line drawing of $G$, at most $O(n^{.4948})$ vertices $v\in V$ are embedded at points $p(v)$. This improves on an earlier bound of $O(\sqrt{n})$ by Goaoc et al. [Discrete Comput. Geom., 42 (2009), pp. 542--569].

We revisit the traveling salesman problem with neighborhoods (TSPN) and obtain several approximation algorithms. These constitute either improvements over previously best approximations achievable in comparable times (for unit disks in the plane), or first approximations ever (for planes, lines and unit balls in 3-space). (I) Given a set of n planes in 3-space, a TSP tour that is at most 2.31 times longer than the optimal can be computed in O(n) time. (II) Given a set of n lines in 3-space, a TSP tour that is at most O(log3 n) times longer than the optimal can be computed in polynomial time. (III) Given a set of n unit disks in the plane (resp., unit balls in 3-space), we improve the approximation ratio using a black box that computes an approximate tour for a set of points (the centers of a subset of the disks or the balls).

We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, nonweighted common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits $\Omega (8.65^n)$ different triangulations. This improves the bound $\Omega (8.48^n)$ achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We obtain a new lower bound of $\Omega(12.00^n)$ for the number of noncrossing spanning trees of the double chain composed of two convex chains. The previous bound, $\Omega(10.42^n)$, stood unchanged for more than 10 years. (iii) Using a recent upper bound of $30^n$ for the number of triangulations, due to Sharir and Sheffer, we show that $n$ points in the plane in general position admit at most $O(68.62^n)$ noncrossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest tours can be exponential in $n$ for points in general position. These tours are automatically noncrossing. Likewise, we show that the number of longest noncrossing tours can be exponential in $n$. It was known that the number of shortest noncrossing perfect matchings can be exponential in $n$, and here we show that the number of longest noncrossing perfect matchings can be also exponential in $n$. It was known that the number of longest noncrossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we re-derive tight bounds for the number of longest and shortest tours with some simpler arguments. We also give a combinatorial characterization of longest tours, which yields an $O(n\log n)$ time algorithm for computing them.

Let S be a set of n points in the unit square [0, 1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). This is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2.

We present a data structure for ray shooting and insertion in the free space between disjoint polygonal obstacles with a total of $n$ vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses $O(n\log n)$ space and preprocessing time, and it supports $m$ successive ray shooting and insertion queries in $O((n+m)\log^2 n + m\log m)$ total time in the real RAM model of computation. We present two applications: (1) Our data structure supports efficient implementation of auto-partitions in the plane, that is, binary space partitions where each partition is done along the supporting line of an input segment. If $n$ input line segments are fragmented into $m$ pieces by an auto-partition, then it can now be implemented in $O(n\log^2n+m\log m)$ time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for $n$ disjoint line segments in the plane to $O(n\log^2 n)$. (2) If we are given disjoint polygonal obstacles with a total of $n$ vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semidynamic ray shooting data structure) requires $O(n^{3/2-\varepsilon/2})$ time using $O(n^{1+\varepsilon})$ space for any $\varepsilon>0$. Our data structure improves the runtime to $O(n\log^2 n)$.

We consider graphs that admit polyline drawings where all crossings occur at the same angle $\alpha\in (0,\frac{\pi}{2}]$. We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has $O(n)$ edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest.

We prove that for every even set of $n$ pairwise disjoint line segments in the plane in general position, there is another set of n segments such that the 2n segments form pairwise disjoint simple polygons in the plane. This settles in the affirmative the Disjoint Compatible Matching Conjecture by Aichholzer et al. [ABD08]. The key tool in our proof is a novel subdivision of the free space around n disjoint line segments into at most n+1 convex cells such that the dual graph of the subdivision contains two edge-disjoint spanning trees.

We obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years. (iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles. (iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them.

We revisit several maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as well as for the Hamiltonian cycle problem: (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio $\frac{2}{\pi+1} \approx 0.4829$. The previous best ratio, due to Alon et al., was $1/\pi \approx 0.3183$. Moreover, the ratio of our algorithm is close to $2/\pi$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio $0.502$ which runs in $O(n \log{n})$ time. The previous ratio, $1/2$, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster $O(n \log{n})$-time algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to $2/\pi$ on a relatively broad class of instances: for point sets with the product $\bf{\langle}$~diameter~$\times$ ~convex hull size $\bf{\rangle}$ much smaller than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. No previous approximation results were known for this problem.

We present a data structure for ray shooting-and-insertion in the free space among disjoint polygonal obstacles with a total of $n$ vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries in O(n log2 n + m log m) total time. We present two applications for our data structure: (1) Our data structure supports efficient implementation of auto-partitions in the plane i.e. binary space partitions where each partition is done along the supporting line of an input segment. If n input line segments are fragmented into m pieces by an auto-partition, then it can now be implemented in O(n log2n+m log m) time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for n disjoint line segments to O(n log2 n). (2) If we are given disjoint polygonal obstacles with a total of n vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the folklore convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semi-dynamic ray shooting data structure) requires O(n3/2-ε/2) time using O(n1+ε) space. Our data structure improves the runtime to O(n log2 n).

A binary space partition (BSP) for a set of disjoint objects in Euclidean space is a recursive decomposition, where each step partitions the space (and some of the objects) along a hyperplane and recurses on the objects clipped in each of the two open halfspaces. The size of a BSP is defined as the number of resulting fragments of the input objects. It is shown that every set of n disjoint line segments in the plane admits a BSP of size O(n log n / log log n). This bound is best possible apart from the constant factor.

A Steiner star for a set P of n points in ℝd connects an arbitrary center point to all points of P, while a star connects a point p ∊ P to the remaining n − 1 points of P. All connections are realized by straight line segments. Fekete and Meijer showed that the minimum star is at most √2 times longer than the minimum Steiner star for any finite point configuration in ℝd. The maximum ratio between them, over all finite point configurations in ℝd, is called the star Steiner ratio in ℝd. It is conjectured that this ratio is 4/π = 1.2732… in the plane and 4/3 = 1.3333… in three dimensions. Here we give upper bounds of 1.3631 in the plane, and 1.3833 in 3-space, thereby substantially improving recent upper bounds of 1.3999, and √2 — 10−-4, respectively. Our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. Our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among n points on the unit sphere, first studied by László Fejes Tóth. It is quite general and yields the first non-trivial estimates below √2 on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in ℝd tends to √2, the upper bound given by Fekete and Meijer, as d goes to infinity. Our estimates on the star Steiner ratios are therefore much closer to the conjectured values in higher dimensions! As it turns out, our estimates as well as the conjectured values of the Steiner ratios (in the limit, for n going to infinity) are related to the classical infinite Wallis product: .

The study of extremal problems on triangle areas was initiated in a series of papers by Erdös and Purdy in the early 1970s. Here we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.

It is shown that for any n disjoint axis-aligned fat rectangles in three-space there is a binary space partition (BSP) of $O(n\log^8 n)$ size and $O(\log^5 n)$ height and it can be constructed in $O(n \,\mathrm{polylog}\, n)$ time. This improves earlier bounds of Agarwal et al. [SIAM J. Comput., 29 (2000), pp. 1422–1448]. On the other hand, for every $n\in \mathbb{N}$, there are n disjoint axis-aligned fat rectangles in $\mathbb{R}^3$ such that their smallest axis-aligned BSP has $\Omega(n\log n)$ size.

It is shown that for every subdivision of the d-dimensional Euclidean space, $d\geq 2$, into n axis-aligned boxes, there is an axis-parallel line that stabs at least $\Omega(\log^{1/(d-1)} n)$ boxes, and this bound is best possible. In general, it is also shown that for every integer k, $0

We propose a low-overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An ε- cut , for any 0 < ε < 1, is a linear separation of ε n nodes in S from a distinguished node, the base station . Our main result is that, by monitoring the status of just O (1/ε) nodes in the network, the base station can detect whenever an ε- cut occurs. Furthermore, this detection comes with a deterministic guarantee that every reported cut has size at least ε n /2. Besides this combinatorial result, we also propose efficient algorithms for finding the O (1/ε) nodes that should act as sentinels , and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on random sampling.

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight-line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines then there is a spanning tree where every barrier is crossed by O(√m) tree edges (connectors), and this bound is asymptotically optimal (spanning tree with low stabbing number). Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Constructions with 3 crossings per barrier and 2n total cost provide a lower bound.We obtain tight bounds on the minimum cost spanning tree in the most exciting special case where the barriers are interior disjoint line segments that form a convex subdivision and there is a point in every cell. In particular, we show that there is a spanning tree such that every barrier is crossed by at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are tight.

Abstract We consider on‐board networks in satellites interconnecting entering signals (inputs) to amplifiers (outputs). The connections are made via expensive switches, each of which has four available links. The paths connecting inputs to outputs should be link‐disjoint. Some of the input signals, called priorities, must be connected to the amplifiers that provide the best quality of service (that is, to some specific outputs). In practice, amplifiers are prone to fail, and the faults cannot be repaired. Therefore, extra outputs have to be built into the network to ensure that every input can be routed to operational outputs. Given three integers, n, p, and f, we would like to design a low‐cost network (where the network cost is proportional to the total number of switches) such that it is possible to route all n inputs to n operational amplifiers, and to route the p priorities to the p best quality amplifiers for any set of f faulty and p best‐quality amplifiers. Let R(n, p, f) be the minimum number of switches of such a network. We prove here that $R(n,p,f)\leq{{n+f}\over{2}}\lceil\log_2p\rceil+{{5}\over{2}}(n-p)+g(f)$ with g a function depending only on f. We then compute R(n, p, f) exactly for a few small values of p and f. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 9–25 2006

We present a multi-dimensional generalization of the Szemerédi-Trotter Theorem, and give a sharp bound on the number of incidences of points and not-too-degenerate hyperplanes in three- or higher-dimensional Euclidean spaces. We call a hyperplane not-too-degenerate if at most a constant portion of its incident points lie in a lower dimensional affine subspace.

For n disjoint line segments in the plane we construct in optimal O(n log n) time an en-compassing tree of maximum degree three such that at every vertex all incident edges lie in a halfplane defined by the incident input segment. In particular, this implies that each vertex is pointed. Furthermore, we show that any set of colored disjoint line segments (for each segment one endpoint is colored red and the other endpoint is colored blue) has an encompassing tree of maximum degree three in which no edge is monochromatic.

We propose a low overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An /spl epsiv/-cut, for any 0</spl epsiv/<1, is a linear separation of /spl epsiv/n nodes in S from a distinguished node, the base station. We show that the base station can detect whenever an /spl epsiv/-cut occurs by monitoring the status of just O(1//spl epsiv/) nodes in the network. Our scheme is deterministic and it is free of false positives: no reported cut has size smaller than 1/2/spl epsiv/n. Besides this combinatorial result, we also propose efficient algorithms for finding the O(1//spl epsiv/) nodes that should act as sentinels, and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on sampling.

Heavy hitters, which are items occurring with frequency above a given threshold, are an important aggregation and summary tool when processing data streams or data warehouses. Hierarchical heavy hitters (HHHs) have been introduced as a natural generalization for hierarchical data domains, including multi-dimensional data. An item x in a hierarchy is called a ϕ-HHH if its frequency after discounting the frequencies of all its descendant hierarchical heavy hitters exceeds ϕn, where ϕ is a user-specified parameter and n is the size of the data set. Recently, single-pass schemes have been proposed for computing ϕ-HHHs using space roughly O(1/ϕ log(ϕn)). The frequency estimates of these algorithms, however, hold only for the total frequencies of items, and not the discounted frequencies; this leads to false positives because the discounted frequency can be significantly smaller than the total frequency. This paper attempts to explain the difficulty of finding hierarchical heavy hitters with better accuracy. We show that a single-pass deterministic scheme that computes ϕ-HHHs in a d-dimensional hierarchy with any approximation guarantee must use Ω(1/ϕd+1) space. This bound is tight: in fact, we present a data stream algorithm that can report the ϕ-HHHs without false positives in O(1/ϕd+1) space.

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space-filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size $O(n^{(d+1)/{3}})$ for all $d \geq 3$ and that such a partition can be computed in time ${O(K\log n)}$, where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions; in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space for which every axis-aligned BSP has $\Omega(n^{\beta(d)})$ size, where $\beta(d)$ converges to $(1+\sqrt{5})/2$ as $d \rightarrow \infty$.

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined into a BSP of size O(n d+1/3), for all d ≥ 3, and that such a partition can be computed in time O(K log n), where K is the size of the BSP produced. Our upper bound on the BSP size is tight for 3-dimensional subdivisions in higher dimensions, this is the first nontrivial result for general full-dimensional boxes. We also present a lower bound construction for a subdivision of n boxes in d-space that requires a BSP of size Ω(n946;(d)), where β(d) converges to (1+ √5 )/2 as d → ∞.

We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is presented in an arbitrary order, and computes a compact summary (called a sketch). The sketch, whose size depends on the approximation parameter ε, can be used to count the number of points inside a query range within additive error εn, where n is the size of the stream. We present several results, deterministic and randomized, for both rectangle and halfplane ranges.

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with or, more generally, as the pth power of the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared to the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to 1 + 2/√3 ≈ 2.15. We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L2 norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.

We show that there is always a binary space partition (BSP) of size O(n log k) and an autopartition of size O(nk) for n disjoint line segments in the plane, assuming that the segments have k distinct orientations. In particular, if k is a constant, these bounds imply that there is a linear-size BSP and autopartition. Our proof is constructive and can be turned into algorithms computing such a BSP or autopartition in O(n 2 ) and O(n 2 k ) times.

It is shown that every set of $n$ points in the plane has an element f rom which there are at least $cn^{6/7}$ other elements at distinct distances, where $c>0$ is a constant. This improves earlier results of Erd\H os, Moser, Beck, Chung, Szemer\'edi, Trotter, and Sz\'ekely.

This paper considers {\sl binary space partition}s (BSP for short) for $n$ disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for $n$ disjoint line segments in the plane is $\Omega (n \log n / \log \log n)$ in the worst case. The best known upper bound due to Paterson and Yao is $O(n \log n)$.