Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Our first contribution is a noncrossing Steiner $(1+\epsilon )$-spanner with $O(n/{\epsilon }^{3/2})$ Steiner vertices. This improves upon the previous best result by Arikati et al. [9], which has $O(n/{\epsilon }^4)$ Steiner vertices.

Arikati et al. [9] construct a set of noncrossing graphs $G_i$ for $1\le i\le k$. The final spanner is ${\bigcup }_{i=1}^k{G}_i$, where a Steiner vertex is added at every edge crossing between $G_i$ and $G_j$, $i\ne j$. Our construction improves on the construction of Arikati et al. [9] in several ways. First, we use fewer graphs $G_i$ when constructing our spanner. Specifically, we use $k=O(1/\sqrt{\epsilon })$ instead of $k=O(1/\epsilon )$ graphs. Whereas the previous construction [9] uses $O(1/\epsilon )$ rotated copies of the point set to approximate the $L_2$ distance with the $L_1$ distance in one of the copies, we instead use $O(1/\sqrt{\epsilon })$ carefully chosen linear transformations to achieve cone-restricted paths between all pairs of points. Second, our graphs $G_i$ are of smaller size than those in Arikati et al. [9]. Both constructions obtain $G_i$ by refining the Balanced Box Decomposition into an axis-parallel spanner under the $L_1$ metric. We are able to use the properties of our linear transformations to obtain the same stretch guarantee using a coarser refinement of the Balanced Box Decomposition. In particular, we obtain $|G_i|=O(n)$, improving on $|G_i|=O(n/{\epsilon }^2)$ in [9]. Third, our construction fills some details that are missing from both [9] and [27, Chapter 4].

Our second contribution is an almost matching lower bound on the number of Steiner vertices in any Euclidean noncrossing Steiner $(1+\epsilon )$-spanner.

To the best of our knowledge, the best previous unconditional lower bound follows from the known size lower bound of $\mathrm{\Omega }(n/\sqrt{\epsilon })$ for Euclidean Steiner $(1+\epsilon )$-spanners [63], which also applies to noncrossing spanners. In this paper, the canonical example to prove lower bounds is the following construction: consider the unit square ${[0,1]}^2$ and let $A$ (resp., $B$) be the set of equally spaced points on the left (resp., right) side of ${[0,1]}^2$ so that the distance between any two consecutive points in $A$ (resp., $B$) is $4\sqrt{\epsilon }$. The point set $P$ is the union of points in $A$ and $B$; see Figure 2 for an illustration. Observe that: (i) the minimum pairwise distance in $P$ is $4\sqrt{\epsilon }$, (ii) the maximum pairwise distance (a.k.a., diameter) in $P$ is $\sqrt{2}$, and (iii) for any $a\in A$ and $b\in B$, the slope of the segment $ab$ is between $-1$ and $1$. Let $G$ be a noncrossing Steiner $(1+\epsilon )$-spanner with the minimal number of Steiner points for $P$.

First, we sketch key ideas behind a weaker $\mathrm{\Omega }(n/\epsilon )$ lower bound (the proof can be found in the full version of the paper).

Let $A_0\subseteq A$ consist of every third point from the bottom third of the left side, and $B_0\subseteq B$ consist of every third point from the top third of the right side. This ensures $|A_0|,|B_0|=\mathrm{\Omega }(1/\sqrt{\epsilon })$ and for each pair $(a,b)\in A_0\times B_0$ the segment $ab$ has slope in $[\frac{1}{3},1]$. For each pair $(a,b)\in A_0\times B_0$, let ${\gamma }_{ab}$ denote a shortest path in $G$ from $a$ to $b$. We apply the result of Bhore and Tóth [18, Lemma 4] to conclude that the set $E_{ab}$ of edges in ${\gamma }_{ab}$ having angle at most $3\sqrt{\epsilon }$ with $ab$ satisfies $\Vert E_{ab}\Vert \ge \frac{7}{9}|ab|$, i.e., the total length of the edges in $E_{ab}$ is at least $\frac{7}{9}|ab|$. Moreover, using a geometric argument, we can show that for distinct pairs $(a,b),(a^{\prime },b^{\prime })\in A_0\times B_0$, the sets $E_{ab}$ and $E_{a^{\prime }{b}^{\prime }}$ are pairwise disjoint.

Now, consider the collection of all ellipses ${ℰ}_{cd}$ with $c,d\in A\cup B$ and slope $-\frac{1}{2}$ (see Figure 3). As these ellipses are pairwise disjoint (Lemma 10), each such ellipse creates a Steiner vertex wherever ${\gamma }_{ab}$ (for $(a,b)\in A_0\times B_0$) intersects it. Since there are $\mathrm{\Theta }(1/\sqrt{\epsilon })$ such disjoint ellipses, and each path ${\gamma }_{ab}$ must cross $\mathrm{\Theta }(1/\sqrt{\epsilon })$ of them, each path ${\gamma }_{ab}$ contains $\mathrm{\Theta }(1/\sqrt{\epsilon })$ Steiner points in these intersections. The bound on the total length combined with the pigeonhole principle implies that the average length of an edge in $E_{ab}$ is $O(\sqrt{\epsilon })$. Consequently, $E_{ab}$ contains at least $\mathrm{\Omega }(1/\sqrt{\epsilon })$ edges. Since there are $\mathrm{\Omega }(1/\epsilon )$ pairs in $A_0\times B_0$ and the sets $E_{ab}$ are edge-disjoint, the total number of edges is $\mathrm{\Omega }(1/\epsilon )\cdot \mathrm{\Omega }(1/\sqrt{\epsilon })=\mathrm{\Omega }(1/{\epsilon }^{3/2})=\mathrm{\Omega }(n/\epsilon )$ for the basic construction. See the full version for a detailed proof.

This lower bound is already stronger than the lower bound of $\mathrm{\Omega }(n/\sqrt{\epsilon })$ that can be derived from the crossing case [63]. However, the limitation of this approach is the fact that the pigeonhole argument can give only $\mathrm{\Omega }(1/\sqrt{\epsilon })$ edges per path ${\gamma }_{ab}$. To improve this to ${\mathrm{\Omega }}_{\mu }(n/{\epsilon }^{3/2-\mu })$ for any $\mu >0$, we will use techniques from geometric measure theory (see the full version for the full proof of Theorem 4). To use these tools, we first need to show that most of the spanner paths have certain properties. Let $M$ be the square of side-length $1/8$ in the middle of ${[0,1]}^2$. We decompose $M$ into an $O(1/\sqrt{\epsilon })\times O(1/\sqrt{\epsilon })$ grid consisting of square windows and analyze the structure of spanner paths within each window. We will also restrict our attention to ellipses ${ℰ}_{ab}$ where the corresponding segment $ab$ has slope $\lambda \in [1/4,3/4]$, and we say that such ellipses and spanner paths are in the positive bundle, or $ab$ has slope $\lambda \in [-3/4,-1/4]$, where the corresponding ellipses and spanner paths belong to the negative bundle. The key properties we establish are:

• $\mathrm{■}$

  Each window $W$ contains crossing ellipses for each slope in the positive and negative bundles.

• $\mathrm{■}$

  Each spanner path ${\gamma }_{ab}$ is adventurous in at most $c/\sqrt{\epsilon }$ windows, meaning it goes outside a narrow strip $R_W({\gamma }_{ab})$ of width $O(\epsilon )$ in only a small number of windows. Here $c$ is a small constant.

• $\mathrm{■}$

  Each spanner path ${\gamma }_{ab}$ is skewed in at most $c/\sqrt{\epsilon }$ windows, meaning its direction deviates significantly from the direction of the segment $ab$ in only a small number of windows. Again, $c$ is a small constant.

• $\mathrm{■}$

  More than half of the windows in $M$ are well-behaved, meaning they are crossed by sufficiently many non-adventurous, non-skewed spanner paths from both the positive and negative bundles.

In a well-behaved window $W$, we can also identify collections ${\mathrm{\Psi }}_W^{+}$ and ${\mathrm{\Psi }}_W^{-}$ of spanner paths such that each path $\gamma \in {\mathrm{\Psi }}_W^{+}\cup {\mathrm{\Psi }}_W^{-}$ is non-adventurous, non-skewed, and the paths and their corresponding strips $R_W(\gamma )$ of width $O(\epsilon )$ have the following properties (see Figure 4):

1. (i)

   Paths in ${\mathrm{\Psi }}_W^{+}$ and ${\mathrm{\Psi }}_W^{-}$ pairwise cross within the window.

2. (ii)

   The directions of the strips $R_W(\gamma )$ corresponding to these paths differ by at least $\mathrm{\Omega }(\sqrt{\epsilon })$.

3. (iii)

   The strips corresponding to distinct paths have small intersection areas, at most half the area of any individual strip.

After this preparation, we want to analyze the number of Steiner vertices. A natural tool would be the classical Szemerédi–Trotter theorem which states that for any set of $\mathrm{\ell }$ lines in the plane, the number of points incident to at least $r$ of these lines is at most $O({\mathrm{\ell }}^2/r^3+\mathrm{\ell }/r)$. Ideally, we would like to apply this theorem to count the number of Steiner vertices incident to many spanner paths. However, the Szemerédi–Trotter theorem does not directly apply, since our spanner paths are not straight lines.

Motivated by problems in geometric measure theory, the Szemerédi–Trotter theorem was generalized to disk-tube incidences [53]. Instead of points and lines, we count intersections between $\delta$-disks (small disks of radius $\delta$) and $\delta$-tubes (long rectangles of width $\delta$). Fu, Gan and Ren [52] recently proved that only $O_{\mu }({|𝒯|}^2/r^3)$ disjoint $r$-rich disks (each intersecting at least $r$ tubes) exist when tubes in $𝒯$ are sufficiently well-spaced and separated in direction.¹¹1The exact definition of sufficiently well-spaced is quite technical and is guided by the $\mu >0$ parameter (see the full version for details).

We apply their theorem to the tubes formed by the strips $R_W({\gamma }_{ab})$ corresponding to the spanner paths with $\delta =\mathrm{\Theta }(\sqrt{\epsilon })$ for every well-behaved window $W$ (see Figure 4). Properties (i), (ii) and (iii) guarantee that the collection of tubes in each well-behaved window $W$ satisfies the spacing and direction separation conditions required by the result of Fu, Gan and Ren [52].

The theorem of Fu, Gan and Ren [52] implies that only $O_{\mu }(1/(\epsilon r^3))$ disjoint $r$-rich $\delta$-disks can intersect tubes in our collection. In their result, there is a technical requirement that $r>{\delta }^{1-2\mu }|{𝒯}_{\max }|$, and so the smallest value of $r$ we can choose is $r={\mathrm{\Omega }}_{\mu }(1/{\epsilon }^{\mu })$. This means that most of the $\mathrm{\Theta }(1/\epsilon )$ crossing points are not covered by the $r$-rich disks. Therefore, there must exist ${\mathrm{\Omega }}_{\mu }(1/\epsilon )$ crossing points where the Steiner vertex is incident to fewer than $r_0={\mathrm{\Theta }}_{\mu }(1/{\epsilon }^{\mu })$ spanner paths from our tube collection. Counting the tube crossings at these low-degree Steiner vertices yields at least ${\mathrm{\Omega }}_{\mu }(1/\epsilon )/r_0^2={\mathrm{\Omega }}_{\mu }(1/{\epsilon }^{1-2\mu })$ such vertices per window, and summing over all $\mathrm{\Omega }(1/\epsilon )$ well-behaved windows gives the ${\mathrm{\Omega }}_{\mu }(1/{\epsilon }^{2-2\mu })$ lower bound on the number of Steiner vertices in $G$. Since $n=\mathrm{\Theta }(1/\sqrt{\epsilon })$, this implies the desired lower bound of ${\mathrm{\Omega }}_{\mu }(n/{\epsilon }^{3/2-2\mu })$. Finally, we scale $\mu$ by a factor of 2. This concludes the sketch of the proof of Theorem 4, see the full version for details.

Theorem 4 leaves a small gap of roughly ${\epsilon }^{o(1)}$ between our upper and lower bounds. We are able to show that this gap can be closed if we restrict our attention to cone-restricted spanners which were used in the construction of Theorem 3. The proof of Theorem 6 uses a generalization of the celebrated Crossing Lemma to so-called degenerate crossings [2, 70].

After covering further related works (Section 1.2) and the preliminaries (Section 2), we provide the construction for our sparse noncrossing Steiner spanner (Section 3). Due to space limitations, complete proofs are deferred to the full version. The proofs of the lower bounds (Theorems 4, 5, and 6) are also deferred to the full version.

The first Euclidean $(1+\epsilon )$-spanners for arbitrary $\epsilon >0$ were obtained independently by Clarkson [37] and Keil [57], and these works also introduced the fixed-angle $\mathrm{\Theta }$-graph (a close variant of the Yao graph [81]) as a basic construction tool. Ruppert and Seidel [76] extended this to ${ℝ}^d$, by giving $(1+\epsilon )$-spanners with $O(n/{\epsilon }^{d-1})$ edges for constant $d$. Le and Solomon [63] proved that this dependence on $\epsilon$ is tight: for every $\epsilon >0$ and constant $d$, there exist point sets in ${ℝ}^d$ for which any $(1+\epsilon )$-spanner must have $\mathrm{\Omega }({\epsilon }^{-(d-1)})$ edges whenever $\epsilon =\mathrm{\Omega }(n^{-1/(d-1)})$.

Another key parameter of a spanner is its lightness. For a set of points, it is the ratio between its total edge weight and the weight of the MST of the point set. Building on the greedy spanner of Althöfer et al. [7], Das et al. [41] proved that this construction achieves constant lightness and stretch $1+\epsilon$ in ${ℝ}^3$, which was later extended to all ${ℝ}^d$ by Das et al. [42]. Rao and Smith [72] established that the greedy $(1+\epsilon )$-spanner in ${ℝ}^d$ has lightness $1/{\epsilon }^{O(d)}$, and a long line of refinements culminated in the bound $O({\epsilon }^{-d}\log (1/\epsilon ))$ by Le and Solomon [63]. Besides achieving small stretch and sparsity²²2The sparsity of a spanner is the ratio of the number of edges in the spanner to the size of MST., spanners are often required to satisfy additional desirable properties such as bounded degree or diameter. There has been extensive work on understanding the optimal trade-offs among these parameters for Euclidean spanners (see, e.g., [10, 17, 47, 45, 61]).

Steiner points can significantly reduce the weight of distance approximation structures (see, e.g., [48, 77]). Note that a Steiner $t$-spanner for a point set $P$ must guarantee stretch $t$ only for point pairs in $P$. Le and Solomon [62] constructed Steiner $(1+\epsilon )$-spanners of sparsity $O({\epsilon }^{(1-d)/2})$ in ${ℝ}^d$ for all $d\ge 2$, and this bound is the best possible [18]. In the plane, Bhore and Tóth [18] constructed Steiner $(1+\epsilon )$-spanners of lightness $O(1/\epsilon )$, this bound is also tight [63]. In dimensions $d\ge 3$, the current best upper and lower bounds for lightness are $\tilde{O}(1/{\epsilon }^{(d+1)/2})$ and $\mathrm{\Omega }(1/{\epsilon }^{d/2})$ [18, 63]. Recent work has also analyzed online algorithms for Euclidean Steiner spanners and obtained several asymptotically tight bounds [15, 19].

Chew [33] first proved the existence of a Euclidean spanner with stretch $\sqrt{10}$ and $O(n)$ noncrossing edges, the stretch was later improved to $2$ [34]. Keil and Gutwin [58] showed that the Delaunay triangulation is a $2.42$-spanner. Later, Bonichon et al. [23] gave tight bounds of $\sqrt{4+2\sqrt{2}}$ for the $L_1$- and $L_{\mathrm{\infty }}$-Delaunay graphs. Subsequently, Bose et al. [25] showed that the Yao graph is a $8\sqrt{2}$-spanner. See the comprehensive survey by Bose and Smid [27] for results on plane spanners up to 2013. Since then, several core questions raised in that survey on plane spanners have seen notable progress. The long-open existence of bounded-degree plane spanners has been resolved for degree $4$ through constructions of Bonichon et al. [24]. Later, Kanj et al. [56] obtained improved stretch bounds. Bose et al. [26] further tightened the trade-off by giving an algorithm to construct degree-$8$ plane spanners with stretch $\approx 4.414$. Dumitrescu and Ghosh [46] strengthened lower bounds on plane-spanner dilation. For degree $3$, progress has been obtained for restricted families of point sets, such as points in convex position [20]. The framework has also been extended to constrained visibility, where van Renssen and Wong [79] showed that visibility graphs among polygonal obstacles admit noncrossing spanners with bounded degree and constant stretch (see also [16, 1] for some recent work on plane spanners in polygonal domains). Further developments include refined stretch analysis for planar variants of $\theta$-like geometric graphs [26], as well as general geometric conditions under which sweepline-based constructions produce planar spanners [65].

We have defined cone-restricted $(1+\epsilon )$-spanners for finite point sets in the plane (Definition 2). Similar concepts have previously been used for other purposes. In a geometric graph $G=(V,E)$, the vertices are distinct points in the plane and the edges are straight-line segments. A geometric graph is strongly monotone [8, 59, 51] if for every $a,b\in V$, there is a $ab$-path $(a=v_0,v_1,\mathrm{\dots },v_m=b)$ in which $\mathrm{\sphericalangle }(\overrightarrow{ab},\overrightarrow{v_{i-1}{v}_i})\le \pi /2$ for all $i=1,\mathrm{\dots },m$. However, this property does not guarantee any stretch factor.

A geometric graph is angle-monotone with width $\gamma$ [21, 43, 68] if for every $a,b\in V$, there is an $ab$-path in which the angle between any two edges is at most $\gamma$. For example, the axis-aligned grid graph induced by $n$ points in the plane is angle monotone with width $(\pi /2)$, and is a $\sqrt{2}$-spanner, however, it uses $O(n^2)$ Steiner vertices. Dehkordi et al. [43] constructed, for $n$ points in ${ℝ}^2$, a plane angle-monotone graph of width $\pi /2$ using $O(n)$ Steiner points. Bonichon et al. [21] showed that the half-${\theta }_6$ graph [22] is angle-monotone with width $2\pi /3$, and $O(n)$ edges, however, it is not necessarily planar. Lubiw and Mondal [68] constructed an angle monotone graph with width $\pi /2$ with $O(n^2\log \log n/\log n)$ edges without Steiner vertices (but with crossings). They also consider a version of the problem with Steiner vertices, however, they require the angle-monotone property for all pairs of vertices (including Steiner vertices), and allow additional crossings. For every $\gamma >0$ and every set $P$ of $n$ points in the plane, they construct a Steiner angle-monotone graph of width $\gamma$ with $O(\frac{n}{\gamma }\log \mathrm{\Phi }(P))$ edges, where $\mathrm{\Phi }(P)$ is an unbounded parameter that depends on the point configurations.

Other constraints imposed on $ab$-path include greedy [66, 71], self-approaching [6] and increasing-chord [40] properties: A geometric graph $G=(V,E)$ is greedy if for every $a,b\in V$, there is an $ab$-path $(a=v_0,v_1,\mathrm{\dots },v_m=b)$ that monotonically gets closest to $b$, that is, for all $i=1,\mathrm{\dots },m$. It is self-approaching if $d(v_j,v_k)\le d(v_i,v_k)$ for all ; and increasing-chord if there is an $ab$-path that is self-approaching in both directions. The self-approaching and increasing-chord properties imply a stretch factor of 5.34 [55], at most $2\pi /3$ [74] (see also [4]), resp., while the greedy property alone does not imply any stretch guarantee.

We also mention a couple of concepts that sound similar to cone-restricted spanners, but are different. The classical $\theta$- and Yao-graphs are constructed by connecting every vertex $v$ to a “closest” point in cones of apex $v$ and aperture $\theta$. They are known to be $O(\theta )$-spanners for $\theta \le \pi /2$, but the $ab$-paths of length $O(\theta )\cdot d(a,b)$ are not necessarily cone-restricted: They may contain (short) edges that make an arbitrary angle with the line segment $ab$.

Another concept, under a similar name, was introduced by Carmi and Smid [29]: A geometric graph is $\theta$-angle-constrained if for every vertex $v\in V$ the angle between any two edges incident to $v$ is at least $\theta$. They note that the classical greedy $(1+\epsilon )$-spanner by Althöfer et al. [7] is $\mathrm{\Omega }(\epsilon )$-angle constrained. For every $\theta \in (0,\pi /3)$, and $n$ points in the plane, one can construct a $\theta$-angle-constrained $(1+O(\theta ))$-spanner in $O(n\log n)$ time [29]; and this is not always possible for $\theta >\pi /3$ [12].

Szemerédi and Trotter [78] proved that $n$ points and $\mathrm{\ell }$ lines in ${ℝ}^2$ determine $O(n^{2/3}{\mathrm{\ell }}^{2/3}+n+\mathrm{\ell })$ point-line incidences, and this bound is the best possible [50]. Motivated by connections to geometric measure theory [80] significant progress was made on a generalization to disk-tube incidences, which is the number of intersections between well-spaced disks of radius $\delta$ and $\delta$-tubes, where a $\delta$-tube is the $\delta$-neighborhood of a line, in a unit square ${[0,1]}^2$; see [39, 44, 52, 53].

The number of disk-tube incidences (used in multiple scales) was instrumental in several recent breakthroughs in combinatorial geometry and geometric measure theory. For example, Heilbronn’s classical problem [75] asks for the minimum $h(n)>0$ such that any set $P$ of $n$ points in the unit square ${[0,1]}^2$ determines a nondegenerate triangle $\mathrm{\Delta }(abc)$ of area at most $h(n)$. A line segment $ab$ is the base of a triangle $\mathrm{\Delta }(abc)$ of area $A$ if and only if there exists a point $c\in P$ in the $\frac{2A}{d(a,b)}$-neighborhood of the line spanned by $ab$. Cohen et al. [38, 39, 82] recently proved $h(n)\ge \mathrm{\Omega }(n^{-8/7-1/2000})$, improving on the previous bound $h(n)\geqq \mathrm{\Omega }(n^{8/7})$ by Komlós et al. [60]. In another recent breakthrough using this machinery, Ren and Wang [73] completely solved the Furstenberg set problem.