The Euclidean Bottleneck Steiner Path Problem and Other Applications of (α,β)-Pair Decomposition

Abstract

We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s, t∈P, and an integer k>0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(nlog² n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. (in Wireless Networks 16, 1033–1043, 2010), who gave an O(n ²logn)-time algorithm. We also study the dual version of the problem, where a value λ>0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ.

Our algorithms are based on two new geometric structures that we develop—an (α,β)-pair decomposition of P and a floor (1+ε)-spanner of P. For real numbers β>α>0, an (α,β)-pair decomposition of P is a collection $\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of pairs of subsets of P, satisfying the following: (i) For each pair $(A_{i},B_{i}) \in\mathcal {W}$, both minimum enclosing circles of A _i and B _i have a radius at most α, and (ii) for any p, q∈P, such that |pq|≤β, there exists a single pair $(A_{i},B_{i}) \in\mathcal{W}$, such that p∈A _i and q∈B _i , or vice versa. We construct (a compact representation of) an (α,β)-pair decomposition of P in time O((β/α)³ nlogn). In some applications, a simpler (though weaker) grid-based version of an (α,β)-pair decomposition of P is sufficient. We call this version a weak (α,β)-pair decomposition of P.

For ε>0, a floor (1+ε)-spanner of P is a (1+ε)-spanner of the complete graph over P with weight function w(p,q)=⌊|pq|⌋. We construct such a spanner with O(n/ε ²) edges in time O((1/ε ²)nlog² n), even though w is not a metric.

Finally, we present two additional applications of an (α,β)-pair decomposition of P. In the first, we construct a strong spanner of the unit disk graph of P, with the additional property that the spanning paths also approximate the number of substantial hops, i.e., hops of length greater than a given threshold. In the second application, we present an O((1/ε ²)nlogn)-time algorithm for computing a one-sided approximation for distance selection (i.e., given k, $1 \le k \le{n \choose2}$, find the k’th smallest Euclidean distance induced by P), significantly improving the running time of the algorithm of Bespamyatnikh and Segal.

1 Introduction

Let P be a set of n points (terminals) in the Euclidean plane. A path in P is a path in the complete graph over P. A path in P between points p, q∈P is a bottleneck path if it minimizes the length of the longest edge in the path. In the Euclidean bottleneck Steiner path (EBSP) problem, we are given P, two terminals s, t∈P, and an integer k, and we need to reduce, as much as possible, the length of the longest edge in a bottleneck path between s and t, by placing k new terminals, called Steiner points. The EBSP problem arises naturally in the design of networks, in particular, wireless communication networks; for example, when it is required to reduce the length of the longest edge (i.e., the maximum transmission range) in a bottleneck path between two transceivers, s and t, in an existing network consisting of n transceivers, by adding k new transceivers. See [17, 18, 25] for more applications in sensor networks.

The Euclidean bottleneck Steiner tree (EBST) problem is closely related to the EBSP problem. In the EBST problem, the goal is to find a spanning tree of P with k Steiner points, minimizing the length of the longest edge in the tree. The EBST problem is NP-hard; moreover, unless P=NP, there is no polynomial-time approximation algorithm for the problem with approximation ratio less than $\sqrt{2}$ [29]. Unlike the EBST problem, the EBSP problem is solvable in polynomial time. Ignoring (only for now) the dependence on k, Hou et al. [17] gave an O(n ²logn)-time exact algorithm for the problem, based on a binary search in the set of all potential lengths (of the longest edge). In this paper, we show that it suffices to consider a certain subset of potential lengths. This subset is of linear size and can be computed efficiently, via an appropriate (α,β)-pair decomposition of P (see below), leading to an O(nlog² n)-time algorithm for the EBSP problem.

We also study the dual version of the EBSP problem: Given P, two terminals s, t∈P, and a constant λ>0, place as few Steiner points as possible, so that the length of the longest edge in a bottleneck path between s and t is at most λ. We present an O(k ^{∗ 2} nlog² n)-time exact algorithm for this problem, where k ^∗ is the number of required Steiner points. The algorithm is based on a floor (1+ε)-spanner of P (see below), which, in turn, is based on an appropriate (α,β)-pair decomposition of P. Again, the corresponding version of the EBST problem is NP-hard (see [24]).

Our algorithms are based on two new geometric structures, which are interesting on their own. For real numbers β>α>0, an (α,β)-pair decomposition (denoted PD _α,β ) of P, is a collection $\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of pairs of subsets of P, satisfying the following two properties: (i) For each pair $(A_{i},B_{i}) \in\mathcal{W}$, both minimum enclosing circles of A _i and B _i have a radius at most α, and (ii) for any p, q∈P, such that |pq|≤β, there exists a single pair $(A_{i},B_{i}) \in\mathcal{W}$, such that p∈A _i and q∈B _i , or vice versa. The weight of a PD _α,β is $\sum_{i=1}^{m} (\lVert A_{i}\rVert+\lVert B_{i}\rVert )$. We construct (a compact representation of) an (α,β)-pair decomposition of P of weight O((β/α)² nlogn) in time O((β/α)³ nlogn). More precisely, we describe how to obtain a PD _α,β of P from a so-called semi-separated pair decomposition of P (with respect to β/α); see below. Sometimes, it is enough to require a weaker version of property (ii), that is, (ii) for any p, q∈P, such that α<|pq|≤β, there exists a single pair $(A_{i},B_{i}) \in\mathcal{W}$, such that p∈A _i and q∈B _i , or vice versa. We refer to a collection of subsets of P satisfying properties (i) and (ii) as a weak (α,β)-pair decomposition of P. Such a weak decomposition of weight O((β/α)² n) can be easily constructed in O((β/α)² nlogn) time.

The second structure that we introduce is the floor (1+ε)-spanner. For ε>0, a floor (1+ε)-spanner of P is a (1+ε)-spanner of the complete graph over P with weight function w′(p,q)=⌊|pq|⌋, where |pq| is the Euclidean distance between points p and q. Notice that w′ is not a metric; in particular, the shortest path between p and q is not necessarily the edge between them. Nevertheless, we construct a floor (1+ε)-spanner of P with O(n/ε ²) edges in time O((1/ε ²)nlog² n). Informally, the edge set of a floor (1+ε)-spanner is the union of the edge set of a minimum spanning tree of P, a set that is obtained from an appropriate (α,β)-pair decomposition of P, and an additional set that is obtained by picking a special edge in each cone around each point in P, as in the construction of a Θ-graph (see [12, 20]).

Finally, we present two additional applications of an (α,β)-pair decomposition. In the first, which demonstrates the full power of an (α,β)-pair decomposition, we construct a spanner of the unit disk graph of P (denoted udg(P)), with some desirable properties. That is, given constants t>1 and 0<λ<1, we construct a spanner G of udg(P) with the following properties: For any two points p, q∈P, there exists a path Π _G (p,q) in G between p and q, such that (i) the length of Π _G (p,q) is bounded by t times the length of the shortest path between p and q in udg(P), (ii) each edge in Π _G (p,q) is of length at most |pq|, and (iii) the number of edges in Π _G (p,q) of length greater than λ is at most the number of such edges in the shortest path between p and q in udg(P). Properties (i) and (ii) simply say that G is a strong t-spanner of udg(P), but property (iii) is new. One can think of λ as a threshold, such that the delay of an edge is substantial if and only if its length is above λ. Property (iii) guarantees that the delay caused by using Π _G (p,q) is not greater than the delay caused by using the shortest path between p and q in udg(P). The number of edges in the spanner G is only O(s ⁴ n) and it can be constructed in time O(s ⁴ nlog² n), where s=s(t,λ) is an appropriate constant.

The second application deals with the well-known distance selection problem. Given an integer k, $1 \le k \le{n\choose2}$, compute the k-th smallest Euclidean distance, d _k , among the $n\choose{2}$ distances determined by pairs of points in P. The best known deterministic algorithm for computing a one-sided approximation of d _k (i.e., a value d such that d _k ≤d≤(1+ε)d _k ) is due to Bespamyatnikh and Segal [5] and runs in time O(nlog³ n). We present a deterministic O(nlogn)-time algorithm for computing a one-sided approximation of d _k , using an appropriate (α,β)-pair decomposition of P.

1.1 Related Work

The EBST problem has received much attention. The best approximation ratio to date is 1.866, achieved by an algorithm of Wang and Li [30]. Bae et al. [4] presented a Θ(nlogn)-time exact algorithm and an O(n ²)-time exact algorithm for the special cases k=1 and k=2, respectively. Li et al. [23] presented a $(\sqrt{2}+\varepsilon)$-approximation algorithm and a matching $\sqrt{2}$ inapproximability result for a special case of the problem where paths may not contain edges between Steiner points. The dual version of the EBST problem has also received considerable attention; see, e.g., [10, 11, 24].

A pair decomposition of a set P of n points in the plane is a collection $\mathcal{W}= \{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of pairs of subsets of P, such that for any two points p, q∈P, there exists a single pair $(A_{i},B_{i}) \in\mathcal{W}$ such that p∈A _i and q∈B _i , or vice versa. Callahan and Kosaraju [8] introduced the well-separated pair decomposition (WSPD). A pair decomposition $\mathcal{W}$ is well separated with respect to a parameter s>0, if, for each pair $(A_{i},B_{i}) \in\mathcal{W}$, the distance between A _i and B _i is at least $s \cdot\max\{r(D_{A_{i}}),r(D_{B_{i}})\}$, where $r(D_{A_{i}})$ and $r(D_{B_{i}})$ are the radii of the minimum enclosing disks of A _i and B _i , respectively. Callahan and Kosaraju showed that a WSPD consisting of m=O(s ² n) pairs can be constructed in O(s ² n+nlogn) time; the weight of the decomposition can be Ω(n ²). This disadvantage has led Varadarajan [28] to define the semi-separated pair decomposition (SSPD). A pair decomposition $\mathcal{W}$ is semi-separated with respect to s, if, for each pair $(A_{i},B_{i}) \in\mathcal{W}$, the distance between A _i and B _i is at least $s \cdot\min\{r(D_{A_{i}}),r(D_{B_{i}})\}$. Varadarajan showed how to compute an SSPD of weight O(nlog⁴ n) in O(nlog⁵ n) time, and used it to efficiently compute a min-cost perfect matching. Subsequently, Abam et al. [2] showed how to construct an SSPD of weight O(s ² nlogn) in O(s ² nlogn) time, and used it to construct region-fault tolerant geometric spanners. Since any pair decomposition has weight Ω(nlogn) (see [6]), the result of Abam et al. [2] is optimal. Recently, Abam and Har-Peled [1] gave alternative constructions of SSPDs.

Geometric spanners have been studied extensively in the last few years. See the book by Narasimhan and Smid [26] for a comprehensive survey of the topic. Θ-graphs were introduced by Clarkson [12] and Keil [20]; they are especially useful for navigation. Notice that any strong (1+ε)-spanner of a set P of n points in the plane is also a (1+ε) spanner of udg(P), and such a spanner with O(n) edges can be constructed in O(nlogn) time (see [31]). Unit disk graphs are often used to model wireless networks; see the book by X.-Y. Li [21] for results on spanners in the context of wireless networks. In particular, substantial research has been done on constructing spanners of unit disk graphs in a local manner; see, e.g., [3, 7, 22]. Roditty and Segal [27] considered spanners containing bounded leg short paths, i.e., short paths consisting of edges whose length does not exceed a prescribed value L.

The best deterministic algorithm to date for the distance selection problem runs in time O(n ^4/3log^2+ε n) (see Katz and Sharir [19]), and the currently best deterministic algorithm for computing a one-sided approximation of the k-th smallest distance runs in time O(nlog³ n+n/ε ²) (see Bespamyatnikh and Segal [5]). Chan [9] presented an O(nlogn+n ^2/3 k ^1/3log^5/3 n) expected-time algorithm for distance selection, and Har-Peled and Raichel [16] recently presented an O(n/ε ²) expected-time algorithm for computing a two-sided approximation of the k-th smallest distance.

1.2 Overview

The rest of the paper is organized as follows. In Sect. 2, we introduce the notion of an (α,β)-pair decomposition of P, and describe how to construct a compact representation for it of weight O((β/α)² nlogn) in time O((β/α)³ nlogn). We also define the notion of a weak (α,β)-pair decomposition of P, which is essentially a grid-based construction. In Sect. 3, we demonstrate the full power of an (α,β)-pair decomposition by constructing in O(nlog² n) time a strong hop-sensitive spanner of udg(P) with O(n) edges. In Sect. 4, we present solutions to the EBSP problem and to its dual version. For the former problem, we present an O(k ² nlogn+nlog² n)-time algorithm, and for the latter problem, we present an O(k ^{∗ 2} nlog² n)-time algorithm. Section 5 deals with the construction of a floor spanner of P. We show how to construct a floor (1+ε)-spanner of P with O(n/ε ²) edges in time O((1/ε ²)nlog² n), for any ε>0. Finally, in Sect. 6, we employ an (α,β)-pair decomposition of P to obtain a more efficient implementation of Bespamyatnikh and Segal’s algorithm for computing a one-sided approximation of the k’th smallest distance induced by P, for $1 \le k \le{n\choose2}$. The new running time is O((1/ε ²)nlogn).

2 (α,β)-Pair Decomposition

Throughout this paper, |pq| denotes the Euclidean distance between points p and q, d(D _i ,D _j ) denotes the distance between the boundaries of two disjoint disks D _i and D _j , r(D) denotes the radius of a disk D, and D _A denotes the smallest enclosing disk of a set of points A.

Given a set P of n points in the plane and two real numbers β>α>0, we are interested in a collection $\mathcal{W}=\{ (A_{1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})\}$ of pairs of subsets of P, satisfying the following two properties:

• (i) For each pair $(A_{i},B_{i})\in\mathcal{W}$, $\max\{ r(D_{A_{i}}),r(D_{B_{i}})\}\le\alpha$, and

• (ii) For any two distinct points p, q∈P such that |pq|≤β, there exists a single pair $(A_{i},B_{i})\in\mathcal{W}$, such that p∈A _i and q∈B _i , or vice versa.

We refer to such a structure as an (α,β)-pair decomposition (denoted, PD _α,β ) of P. The size of a PD _α,β is the number of pairs, m, and its weight is $\sum_{i=1}^{m}(\Vert A_{i}\Vert+\Vert B_{i}\Vert)$, where ∥A _i ∥ (resp. ∥B _i ∥) is the cardinality of A _i (resp. B _i ). In this section, we show how to construct in O(c ⁴ nlogn) time a PD _α,β of P of size O(c ⁴ n) and weight O(c ⁴ nlogn), where $c=\frac{\beta}{\alpha}$.

Sometimes, it is enough to require property (ii′) below instead of property (ii).

(ii′):

For any two distinct points p, q∈P such that |pq|≤β, exactly one of the following two conditions holds. There exists a subset C among the subsets A ₁,…,A _m ,B ₁,…,B _m such that both p and q belong to C, or there exists a single pair $(A_{i},B_{i})\in\mathcal{W}$ such that p∈A _i and q∈B _i , or vice versa.

We refer to a collection of pairs of subsets of P satisfying properties (i) and (ii′) as a weak (α,β)-pair decomposition (denoted, $\mathrm{PD}^{\mathrm{w}}_{\alpha,\beta}$) of P.

2.1 PD _α,β of P

Let A and B be two sets of points in the plane and let s>0 be a constant. We say that A and B are semi-separated with respect to s (or with separation s), if d(D _A ,D _B )≥s⋅min{r(D _A ),r(D _B )}.

Definition 2.1

Let P be a set of n points in the plane and let s>0 be a constant. A semi-separated pair decomposition (SSPD) of P with respect to s is a collection {(A ₁,B ₁),…,(A _m ,B _m )} of pairs of subsets of P, such that:

• (i) A _i and B _i are semi-separated with respect to s, for i=1,…,m, and

• (ii) For any two distinct points p, q∈P, there exists a single pair (A _i ,B _i ) in the collection, such that p∈A _i and q∈B _i , or vice versa.

Abam et al. [2] showed that an SSPD of P of size O(s ² n) and weight O(s ² nlogn) can be constructed in O(s ² nlogn) time. We construct a PD _α,β of P from this SSPD.

Let P be a set of n points in the plane and let β>α>0 be two real numbers. We first construct in O(s ² nlogn) time an SSPD $\mathcal{S}$ of P with respect to s=β/α. Next, we remove all pairs $(A_{i},B_{i})\in\mathcal{S}$ for which $d(D_{A_{i}},D_{B_{i}}) > \beta$. Denote by $\mathcal{W}$ the collection of pairs surviving this step, and notice that for any two distinct points p, q∈P such that |pq|≤β, there exists a single pair $(A_{i},B_{i})\in\mathcal{W}$, such that p∈A _i and q∈B _i (or vice versa), and for each pair $(A,B)\in \mathcal{W}$, we have min{r(D _A ),r(D _B )}≤β/s=α.

Now, for each pair $(A,B)\in\mathcal{W}$, we either keep it in $\mathcal{W}$, if max{r(D _A ),r(D _B )}≤α, or we replace it by a collection of O((β/α)²) pairs, otherwise. Consider a pair $(A,B)\in\mathcal{W}$ such that max{r(D _A ),r(D _B )}>α, and assume without loss of generality that r(D _A )<r(D _B ). Put γ _A =r(D _A )≤α, and let o _A be the center of D _A . Let h be the half-plane containing D _B that is defined by the line through o _A perpendicular to the line through o _A and the center of D _B . We partition h into t=⌈π/θ⌉ cones C ₁,…,C _t , each with apex at o _A and angle at most θ, where $\theta=2\arcsin(\frac{\alpha}{2(\beta +\gamma _{A})} )$; see Fig. 1(a). Let B ⁽ⁱ⁾ be the subset consisting of points of B that lie in D _B ∩C _i and whose distance from o _A is at most β+γ _A . We now explain how to partition B ⁽ⁱ⁾ into disjoint subsets $B^{(i)}_{1},\ldots ,B^{(i)}_{l}$, such that $B^{(i)}_{j}$ is contained in a disk of radius at most α, for j=1,…,l.

Fig. 1

(a) The cones and the subset B ⁽ⁱ⁾. (b) Partitioning B ⁽ⁱ⁾ into $B^{(i)}_{1},\ldots,B^{(i)}_{l}$

Let x and y be the two points on C _i ’s boundary, whose distance from o _A is β+γ _A , and let Δ denote the triangle xo _A y. Since ∠xo _A y≤θ, we have $|xy| \le2(\beta +\gamma_{A}) \cdot\sin{\frac{\theta}{2}} = 2(\beta+\gamma_{A}) \cdot \frac {\alpha}{2(\beta+\gamma_{A})} = \alpha$. We now divide Δ into at most l=⌈β/α⌉ trapezoids $\mathcal {T}_{1},\ldots ,\mathcal{T}_{l}$, each with base parallel to xy and height α; see Fig. 1(b). Next, we partition B ⁽ⁱ⁾ into l disjoint subsets $B^{(i)}_{1},\ldots,B^{(i)}_{l}$, such that $B^{(i)}_{j}$ is the set of points of B ⁽ⁱ⁾ that lie in $\mathcal{T}_{j}$, for j=2,…,l, and $B^{(i)}_{1}$ is the set of points of B ⁽ⁱ⁾ that lie either in $\mathcal{T}_{1}$ or to the right of xy.

Clearly, each subset $B^{(i)}_{j}$ is contained in a disk of radius at most α (actually, $\frac{\sqrt{2}}{2}\alpha$). Therefore, for each pair $(A,B^{(i)}_{j})$, we have $\max\{r(D_{A}),r(D_{B^{(i)}_{j}})\} \le \alpha$. In addition, for any two points p∈A and q∈B ⁽ⁱ⁾, there exists a single pair $(A,B^{(i)}_{j})$, such that $q\in B^{(i)}_{j}$. After repeating the above procedure for each of the cones C ₁,…,C _t , we replace the pair (A,B) with the collection of t⋅l pairs $\{(A,B^{(1)}_{1}),\ldots,(A,B^{(1)}_{l}),\ldots ,(A,B^{(t)}_{1}),\ldots ,(A,B^{(t)}_{l})\}$.

Clearly, we have obtained a PD _α,β of P. The following theorem summarizes its properties.

Theorem 2.2

Given a set P of n points in the plane and two real numbers β>α>0, a PD _α,β of P of size O(c ⁴ n) and weight O(c ⁴ nlogn) can be computed in O(c ⁴ nlogn) time, where c=β/α. A compact representation of PD _α,β of weight O(c ² nlogn) can be computed in O(c ³ nlogn) time.

Proof

An SSPD of size O((β/α)² n) and weight O((β/α)² nlogn) can be computed in O((β/α)² nlogn) time [2]. For each pair $(A,B) \in\mathcal{W}$ (i.e., for each (A,B) of the SSPD such that d(D _A ,D _B )≤β), we first partition B into t disjoint subsets B ⁽¹⁾,…,B ^(t), and then partition each B ⁽ⁱ⁾ into at most l disjoint subsets $B^{(i)}_{1},\ldots,B^{(i)}_{l}$. That is, B is partitioned into t⋅l disjoint subsets, and this can clearly be done in time (t+l)⋅∥B∥. Since t=⌈π/θ⌉=O(β/α) ¹ and l=O(β/α), the resulting PD _α,β is of size² O(t⋅l⋅(β/α)² n)=O((β/α)⁴ n) and weight

$$\begin{aligned} \sum_{(A,B) \in\mathcal{W}}\sum_{i=1}^{t} \sum_{j=1}^{l} \bigl(\Vert A\Vert+ \bigl\Vert B^{(i)}_j \bigr\Vert \bigr) &= \sum \bigl(t \cdot l \cdot \Vert A\Vert+\Vert B\Vert \bigr) \\ &\le t \cdot l \cdot\sum \bigl(\Vert A\Vert+\Vert B\Vert \bigr) \\ &= O \bigl(t \cdot l \cdot(\beta/\alpha)^2n\log{n} \bigr) = O \bigl(( \beta/\alpha)^4n\log{n} \bigr), \end{aligned}$$

and its total construction time is O(t⋅l⋅(β/α)² nlogn)=O((β/α)⁴ nlogn). In the compact representation of PD _α,β , we keep only one copy of each set A of the SSPD (instead of t⋅l copies). □

2.2 $\mathrm{PD}^{\mathrm{w}}_{\alpha,\beta}$ of P

Lay a regular grid over P, such that the side length of a grid cell is α/2, and set P _σ =P∩σ, for each grid cell σ. Next, for each pair of non-empty grid cells σ, σ′ (σ≠σ′), such that the distance between the boundaries of their enclosing disks is at most β (where the distance is 0 if the disks intersect), add the pair {P _σ ,P _σ′} to $\mathcal{W}$. Clearly, the collection of pairs $\mathcal{W}$ satisfies properties (i) and (ii′) above, and the size and weight of $\mathcal{W}$ is only O((β/α)² n). It is also easy to see that $\mathcal{W}$ can be computed in O((β/α)² nlogn) time, using orthogonal range searching. We thus have the following.

Theorem 2.3

Given a set P of n points in the plane and two real numbers β>α>0, a $\mathrm{PD}^{\mathrm{w}}_{\alpha,\beta}$ of P of size and weight O(c ² n) can be computed in O(c ² nlogn) time, where c=β/α.

The advantage of the weak version of an (α,β)-pair decomposition is obvious; it is simpler, the power of the factor β/α in the size and weight bounds is only 2 rather than 4, and moreover the weight bound is O(n) rather than O(nlogn). However, in some cases we do need the strong version, as in the construction of a hop-sensitive spanner in Sect. 3 below.

Remark

Notice that a $\mathrm{PD}^{\mathrm{w}}_{\alpha,\beta}$ (that is constructed according to the description above) actually satisfies a slightly stronger property (ii′); this will become useful in Sect. 6.

(ii′′):

For any two distinct points p, q∈P such that |pq|≤β, exactly one of the following two conditions holds. There exists a single subset P _σ such that both p and q belong to P _σ , or there exists a single pair $\{P_{\sigma}, P_{\sigma'}\} \in\mathcal{W}$ such that p∈P _σ and $q \in P_{\sigma}'$, or vice versa. Moreover, if α<|pq|≤β, then the latter condition holds.

3 Hop-Sensitive Spanner

In this section we demonstrate the power of an (α,β)-pair decomposition by using it to construct a spanner of a unit disk graph with some desirable properties. Let P be a set of n points in the plane and let E={{p,q} | p,q∈P,0<|pq|≤1}. The graph (P,E) is called the unit disk graph of P and is denoted udg(P). A Euclidean graph G over P is a strong t-spanner of udg(P), for a given constant t>1, if for any two points p, q∈P there exists a path Π _G (p,q) in G between p and q, such that (i) Π _G (p,q) is a t-spanning path, i.e., its length is bounded by t times the length of the shortest path between p and q in udg(P), and (ii) each edge in Π _G (p,q) is of length at most |pq|. Finally, let 0<λ<1 be a constant. A path Π _G (p,q) in G between p and q is a λ-hop-sensitive path, if the number of edges in Π _G (p,q) of length greater than λ is at most the number of such edges in the shortest path between p and q in udg(P).

Our goal in this section is to construct a strong λ-hop-sensitive t-spanner of udg(P). That is, given constants t>1 and 0<λ<1, we wish to construct a Euclidean graph G over P, such that for any two points p, q∈P, there exists a path Π _G (p,q) in G between p and q, such that (i) Π _G (p,q) is a t-spanning path, (ii) each edge in Π _G (p,q) is of length at most |pq|, and (iii) Π _G (p,q) is a λ-hop-sensitive path. Moreover, we require that the number of edges in G is only O(n). Such a spanner is useful when, e.g., the cost of an edge is proportional to its length and the delay of an edge is negligible if its length is at most λ but substantial otherwise. For the rest of this section, we assume that t≤2, since otherwise, we simply set t=2 in our construction.

We construct such a spanner from an appropriate (α,β)-pair decomposition of P. Recall that in the construction of an (α,β)-pair decomposition (Sect. 2.1), we set the separation (of the underlying SSPD) to $s=\frac{\beta}{\alpha}$ and the angle (of the cones) to $\theta =2\arcsin(\frac{\alpha}{2(\beta+\gamma_{A})} )$. However, when t is small (i.e., t→1), these values might not be suitable (i.e., not big enough, in the case of s, or not small enough, in the case of θ) to obtain a t-spanner. We thus first update the values of s and θ to accommodate t as well; we denote the new values by s ^∗ and θ ^∗.

Given P, and constants t>1 and 0<λ<1, set $\alpha= \frac{\lambda}{2}$ and β=1. Moreover, set $s' = \frac {4}{\sqrt{t} - 1}$ and s ^∗=max{s,s′}. Let ψ be such that $\cos\psi- \sin\psi= \frac{1}{\sqrt{t}}$, that is, let $\psi= \arccos(\frac{1}{\sqrt{2t}}) - \frac{\pi}{4}$, and set θ′=ψ/2 and θ ^∗=min{θ,θ′}. We construct an (α,β)-pair decomposition $\mathcal{W}=\{ (A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of P, by constructing an SSPD of P with respect to separation s ^∗ (instead of s) and using the angle θ ^∗ (instead of θ), as described in Sect. 2.1. Next, we construct G from $\mathcal{W}$. Initially, G’s edge set E is empty. We add at most m edges to E as follows. For each pair $(A_{i},B_{i}) \in\mathcal{W}$, we find the closest pair of points (p _i ,q _i ) in A _i ×B _i and add the edge {p _i ,q _i } to E if its length is at most 1. We now claim that G has the desired properties.

Lemma 3.1

G has properties (i)–(iii).

Proof

It is enough to show that, for each edge {p,q} of udg(P), there exists a path Π _G (p,q) in G between p and q, such that (i) its length is bounded by t|pq|, (ii) each edge in Π _G (p,q) is of length at most |pq|, and (iii) the number of edges in Π _G (p,q) of length greater than λ is at most 1, if |pq|>λ, and 0, otherwise. Given an edge {p,q} of udg(P), Algorithm 1 below constructs a path Π _G (p,q) in G between p and q.

Algorithm 1

Π _G (p,q)

Consider the path Π _G (p,q)=(p=p ₀,…,a ₀,p ₁,…,a ₁,…,p _m−1,…,a _m−1,p _m ) obtained by Algorithm 1. First notice that if {p,q}∈E, then Π _G (p,q)=(p,q). Moreover, since s ^∗ is sufficiently large ($s^{*} \ge s \ge\frac {4}{\sqrt{t}-1} > 8$), |p _i a _i |<|pq|, and the angle between |p _i q| and |p _i p _i+1| is at most 2θ ^∗≤2θ′=ψ, for 0≤i≤m−1, and therefore

$$ |p_{i+1}q| \leq|p_iq| - (\cos\psi- \sin \psi)|p_ip_{i+1}| < |p_iq| $$

(∗)

(see [26], Lemma 4.1.4). The latter inequalities imply that the algorithm terminates and that indeed p _m =q (since, as i increases the distance between p _i and q decreases).

Before we proceed to prove that Π _G (p,q) has the desired properties, consider the following “virtual” path:

$$\varPi_V(p,q) = (p=p_0, p_1, \dots, p_m=q). $$

We call it virtual since it is not necessarily in G. We bound the length of Π _V (p,q) as in [26] (where it is called a Θ-walk or a ψ-walk in our notation). From (∗), we have

$$|p_ip_{i+1}| \leq\frac{|p_iq| - |p_{i+1}q|}{\cos\psi- \sin\psi} = \sqrt{t}\bigl(|p_iq| - |p_{i+1}q|\bigr) , $$

for 0≤i≤m−1. Therefore, the length of Π _V (p,q) is at most

$$\sum_{i=0}^{m-1} |p_ip_{i+1}| \le\sqrt{t} \sum_{i=0}^{m-1}\bigl(|p_iq| - |p_{i+1}q|\bigr) \le\sqrt{t} \bigl(|p_0 q| - |p_mq|\bigr) \le\sqrt{t} |pq| . $$

We conclude that the length of Π _V (p,q) is at most $\sqrt{t}|pq|$.

We now prove that Π _G (p,q) satisfies properties (i)–(iii). The proof is by induction on the rank of the edges of udg(P) sorted by length.

Base: {p,q} is the shortest edge of udg(P). In this case, {p,q}∈E, and therefore, by the observation above, Π _G (p,q)=(p,q) and satisfies properties (i)–(iii).

Induction hypothesis: For any edge {u,v} of udg(P), such that |uv|<|pq|, the path Π _G (u,v) between u and v in G satisfies properties (i)–(iii).

Inductive step: Since $\mathcal{W}$ is a refinement of an SSPD, we have the following two inequalities for any 0≤i≤m−1 (see [26]):

• (a) $|p_{i} a_{i}| \leq\frac{2}{s^{*}}|a_{i}p_{i+1}| \leq\frac {2}{s^{*}}|pq|$, and

• (b) $|p_{i} p_{i+1}| \leq(1 + \frac{2}{s^{*}})|a_{i}p_{i+1}|$.

We first prove that Π _G (p,q) has properties (ii) and (iii). We cut Π _G (p,q) into three paths, the path between p and a ₀ (i.e., π ₀=Π _G (p,a ₀)), the single edge (a ₀,p ₁), and the path between p ₁ and q (which is Π _G (p ₁,q), as can be easily verified). Since |p ₀ a ₀|<|pq| (by inequality (a)) and since |p ₁ q|<|pq| (by (∗)), we can apply the induction hypothesis to {p ₀,a ₀} and to {p ₁,q}. By applying the induction hypothesis to the first pair, we get that π ₀ has property (ii), with respect to |p ₀ a ₀|≤2α≤λ<1, and therefore it does not contain edges of length greater than λ. Similarly, by applying the induction hypothesis to the second pair, we get that Π _G (p ₁,q) has property (ii), with respect to |p ₁ q|≤2α≤λ<1, and therefore it also does not contain edges of length greater than λ. Finally, since |p ₀ p ₁|≤|pq|, we conclude that Π _G (p,q) has properties (ii) and (iii).

We now prove that Π _G (p,q) is also a t-spanning path. By inequality (a) and by the induction hypothesis we have that w(π _i )≤t|p _i a _i | (where w(π _i ) is the length of π _i ), and therefore, by inequality (a) again, $w(\pi_{i}) \le\frac{2t}{s^{*}}|a_{i}p_{i+1}|$. The length of Π _G (p,q) is at most

$$\begin{aligned} \sum_{i=0}^{m-1} \bigl(w(\pi_i) + |a_ip_{i+1}| \bigr) &\leq\sum _{i=0}^{m-1} \biggl(\frac{2t}{s^*}|a_ip_{i+1}| + |a_ip_{i+1}| \biggr) \\ &{}= \biggl(\frac{2t}{s^*} + 1 \biggr) \sum_{i=0}^{m-1} |a_ip_{i+1}| \leq \biggl(\frac{2t}{s^*} + 1 \biggr) \sum_{i=0}^{m-1} |p_ip_{i+1}| \\ &{}= \biggl(\frac{2t}{s^*} + 1 \biggr) w \bigl(\varPi_V(p,q) \bigr) \leq \biggl(\frac{2t}{s^*} + 1 \biggr) \sqrt{t}|pq| \\ &{}\leq \biggl(\frac{4}{4/(\sqrt{t}-1)} + 1 \biggr) \sqrt{t}|pq| = t|pq|. \end{aligned}$$

 □

The following theorem summarizes the result of this section.

Theorem 3.2

Let P be a set of n points in the plane, and let t>1 and 0<λ<1 be two constants. Then, one can construct a strong λ-hop-sensitive t-spanner of udg(P) with O(s ^{∗ 4} n) edges in O(s ^{∗ 4} nlog² n) time.

Remark

Our spanner G actually satisfies a stronger version of property (iii): For any two points p, q∈P and for any path ρ in udg(P) between p and q, there exists a path in G, such that the number of edges in it of length greater than λ is at most the number of such edges in ρ.

4 Euclidean Bottleneck Steiner Paths

Let P be a set of n terminals in the plane. For two terminals p, q∈P, let δ(p,q) denote a path in P (i.e., in the complete Euclidean graph over P) between p and q, and let bn(δ(p,q)) be the bottleneck of δ(p,q), i.e., bn(δ(p,q)) is the length of a longest edge in δ(p,q). A bottleneck path between p and q in P, denoted δ ^∗(p,q), is a path δ(p,q) with the smallest bottleneck.

Given a set P of n terminals in the plane, two terminals s, t∈P, and an integer k, the goal in the Euclidean bottleneck Steiner path (EBSP) problem is to place at most k new terminals, called Steiner points, so as to minimize the bottleneck of a bottleneck path between s and t. (We refer to such a path as a bottleneck Steiner path.)

Problem 1

(EBSP)

Given a set P of n terminals in the plane, two terminals s,t∈P, and a positive integer k, find a bottleneck Steiner path between s and t with at most k Steiner points.

The dual version of the EBSP problem is defined as follows.

Problem 2

(Dual-EBSP)

Given a set P of n terminals in the plane, two terminals s, t∈P, and a constant λ>0, find a Steiner path between s and t with bottleneck at most λ that uses as few Steiner points as possible.

The decision version of both problems is the following.

Problem 3

(Dec-EBSP)

Given a set P of n terminals in the plane, two terminals s, t∈P, a positive integer k, and a constant λ>0, does there exist a Steiner path between s and t with at most k Steiner points and bottleneck at most λ?

Problems 1 and 2 are dual in the following sense. Assume we have computed (perhaps implicitly) a finite set of values, such that the optimum bottleneck (resp., the optimum number of Steiner points) is in the set (i.e., we have restricted the search space to some finite set). Then we can solve Problem 1 (resp., Problem 2) by applying binary search to this set of values, using an efficient algorithm for Problem 2 (resp., Problem 1) as the decision algorithm.

We first observe that we may assume that the Steiner points must lie on edges of the complete graph over P. (Consider an optimal Steiner path and two consecutive original terminals x and y in the path. If the subpath between x and y passes through l Steiner points, then one can replace them with l evenly spaced Steiner points on the edge between x and y, without increasing the bottleneck of the path.) Notice, however, that it is not enough to consider only the edges of a minimum spanning tree of P, as shown in Fig. 2. By the observation above, there exists a trivial search space for Problem 1 of size O(kn ²): For each edge e in the complete graph over P, add the k+1 values $|e|, \frac{|e|}{2}, \ldots, \frac {|e|}{k+1}$ to the search space.

Fig. 2

(a) A minimum spanning tree of P. (b) An optimal location for a single Steiner point

In Sect. 4.1, we present a simple algorithm for solving Dec-EBSP. We then use this algorithm, in Sect. 4.2, after computing a (non-trivial) linear-size search space, to solve EBSP. In Sect. 4.3, we study the dual version of EBSP.

4.1 Solving Dec-EBSP

Given a set P of n terminals in the plane, two terminals s, t∈P, a positive integer k, and a constant λ>0, the following simple algorithm decides whether there exists a Steiner path between s and t in P with at most k Steiner points and bottleneck at most λ. Assume for now that G=(P,E) is the complete graph over P.

For each edge e∈E, we assign a weight w(e) equal to the minimum number of Steiner points needed to traverse e by steps of size at most λ; see Algorithm 1. We now apply Dijkstra’s algorithm [13] to find a shortest path δ(s,t) between s and t in G, with respect to the weight function w. It is easy to see that w(δ(s,t)) Steiner points are both necessary and sufficient to achieve bottleneck at most λ.

Lemma 4.1

Given a set P of n terminals in the plane, two terminals s, t∈P, and a constant λ>0, one can decide in O(|E|+nlogn) time whether there exists a Steiner path between s and t in G with at most k Steiner points and bottleneck at most λ.

Note that an O(n ²)-time algorithm for Dual-EBSP can be derived immediately from Algorithm 2. Moreover, in view of the remark preceding Sect. 4.1, an O(kn ²+n ²logn)-time algorithm for EBSP can be derived from Algorithm 2. (Actually, the latter bound can be improved by observing that the search space can be represented implicitly as a sorted matrix; see the complexity analysis at the end of Sect. 4.2.)

Algorithm 2

Dec-EBSP(G=(P,E), s, t, k, λ)

4.2 Solving EBSP

In this section we assume that k=o(n). We develop an O(nlog² n)-time algorithm for EBSP, if k is a constant. More precisely, the running time of our algorithm is O(k ² nlogn+nlog² n).

Let G=(P,E) be the complete graph over P. Let $\delta_{G}^{*}(s,t,k)$ be a bottleneck Steiner path between s and t in G with at most k Steiner points and let λ ^∗ denote its bottleneck. We first compute a 2-approximation of λ ^∗.

Lemma 4.2

Let t′>1 be a constant and let G′ be a t′-spanner of G. Then, $bn(\delta_{G'}^{*}(s,t,k)) \le t' \cdot\lambda^{*}$.

Proof

Let δ _G (s,t) be the path between s and t in G that is obtained from $\delta_{G}^{*}(s,t,k)$ by removing the Steiner points. Consider any edge e _i =(p,q) in δ _G (s,t) and let k _i be the number of Steiner points located on e _i in $\delta_{G}^{*}(s,t,k)$. (Recall that we showed that we may assume that the Steiner points in $\delta_{G}^{*}(s,t,k)$ lie on edges of G.) Since G′ is a t′-spanner of G, there exists a path δ _G′(p,q) in G′ of length at most t′⋅|e _i |. Thus, by locating k _i evenly spaced Steiner points on δ _G′(p,q), we obtain a Steiner path between p and q in G′ of bottleneck at most $\frac{|\delta_{G'}(p,q)|}{k_{i}+1} \le t'\cdot\frac{|e_{i}|}{k_{i}+1} \le t'\cdot\lambda^{*}$, where $|\delta _{G'}(p,q)|=\sum_{e\in\delta_{G'}(p,q)}|e|$. □

Let G′=(P,E′) be a t′-spanner of G. Let $\delta_{G'}^{*}(s,t,k)$ be a bottleneck Steiner path between s and t in G′ with at most k Steiner points and let λ′ be its bottleneck. Finally, let $S= \{\frac{|e|}{i} : e \in E', i \in\{1,\ldots, k+1 \} \}$ and notice that λ′∈S. It is well known that G′ has O(n) edges and can be constructed in O(nlogn) time; see [26]. Thus, we can compute λ′ by performing a binary search in S, and using Algorithm 2 to decide whether, for a given value λ∈S, there exists a path from s to t in G′ with at most k Steiner points and bottleneck at most λ.

Corollary 4.3

For any constant t′>1, a Steiner path between s and t in P with at most k Steiner points and bottleneck at most t′⋅λ ^∗, can be computed in O(nlog² n) time.

Proof

Compute a t′-spanner G′ of G in O(nlogn) time, and then compute a bottleneck Steiner path between s and t in G′ with at most k Steiner points, as described above. Notice that S can be represented implicitly by a (k+1)×|E′| sorted matrix, and selection in S can be performed in O(klogn) time [15] (see the analysis preceding Theorem 4.6). Therefore, the total running time is O((klogn+nlogn)logn)=O(nlog² n). □

We now set t′=2 and apply Corollary 4.3 to obtain, in O(nlog² n) time, a value λ′, such that λ′≤2λ ^∗. More precisely, $\frac{\lambda'}{2} \le\lambda^{*} \le \lambda'$.

Our next goal is to characterize the edges of E on which we may want to place Steiner points in the construction of a bottleneck Steiner path. Notice that it does not make sense to locate a Steiner point on an edge e∈E with $|e| \le\frac{\lambda'}{2}$ or |e|>(k+1)λ′. Thus, Steiner points will be located only on edges that belong to the set $E''=\{e \in E : \frac{\lambda'}{2} < |e| \le(k+1)\lambda'\}$.

Let T be a minimum spanning tree of G. Let T ₁,T ₂,…,T _m be the forest $\mathcal{T}$ obtained from T by removing the edges of length greater than $\frac{\lambda'}{2}$; see Fig. 3. Let V _i ⊂P be the vertex set of T _i , for i=1,…,m. For 1≤i, j≤m, i≠j, let e _i,j be the shortest edge between a terminal in V _i and a terminal in V _j , that is, |e _i,j |=d(V _i ,V _j ). Finally, let E ^∗ be the set consisting of all edges e _i,j , for which |e _i,j |≤(k+1)λ′. Notice that all edges of E ^∗ are of length greater than $\frac{\lambda'}{2}$, and, therefore, E ^∗⊆E″. In the following lemmas, we show that it is sufficient to consider the edges of E ^∗ (together with the edges of $\mathcal{T}$) in the construction of a bottleneck Steiner path, that |E ^∗|=O(k ² n), and that E ^∗ can be computed efficiently.

Fig. 3

The edges of $\mathcal{T}$ (solid lines) and E ^∗ (dashed lines)

Lemma 4.4

There exists a bottleneck Steiner path $\delta_{G}^{*}(s,t,k)$, such that, for any two consecutive (original) terminals p and q in $\delta _{G}^{*}(s,t,k)$,

• (i) if $|pq| \le\frac{\lambda'}{2}$, then $(p,q)\in\mathcal {T}$, and

• (ii) if $|pq| > \frac{\lambda'}{2}$, then (p,q)∈E ^∗.

Proof

Let δ _G (s,t,k) be a bottleneck Steiner path between s and t. Consider any two consecutive terminals p ₁ and q ₁ in δ _G (s,t,k). If $|p_{1}q_{1}| \le\frac{\lambda'}{2}$ but $(p_{1},q_{1}) \notin\mathcal{T}$, then p ₁ and q ₁ are in the same subset V _i , for some 1≤i≤m, and there exists a path $\delta_{T_{i}}(p_{1},q_{1})$ between p ₁ and q ₁ in T _i , such that each edge in $\delta _{T_{i}}(p_{1},q_{1})$ is of length at most |p ₁ q ₁|. We replace the edge (p ₁,q ₁) in δ _G (s,t,k) by the path $\delta_{T_{i}}(p_{1},q_{1})$ to obtain a new bottleneck Steiner path between s and t that satisfies condition (i) (and (ii)) (for the subpath between p ₁ and q ₁).

If $|p_{1}q_{1}| > \frac{\lambda'}{2}$ but (p ₁,q ₁)∉E ^∗, then we distinguish between two cases:

Case 1. p ₁, q ₁∈V _i , for some 1≤i≤m. Then there exists a path $\delta_{T_{i}}(p_{1},q_{1})$ between p ₁ and q ₁ in T _i , such that each edge in $\delta_{T_{i}}(p_{1},q_{1})$ is of length at most |p ₁ q ₁|. As above, we replace the edge (p ₁,q ₁) in δ _G (s,t,k) by the path $\delta_{T_{i}}(p_{1},q_{1})$ to obtain a new bottleneck Steiner path between s and t that satisfies condition (i) (and (ii)) (for the subpath between p ₁ and q ₁).

Case 2. p ₁∈V _i and q ₁∈V _j , for i≠j. By the optimality of δ _G (s,t,k), |p ₁ q ₁|≤(k+1)λ′. Hence, d(V _i ,V _j )≤(k+1)λ′ and the edge e _i,j =(p,q), whose length is d(V _i ,V _j ), belongs to the set E ^∗. Let l≥0 be the number of Steiner points between p ₁ and q ₁ in δ _G (s,t,k). We replace the subpath of δ _G (s,t,k) between p ₁ and q ₁ by the path that is formed by concatenating the paths $\delta _{T_{i}}(p_{1},p)$, the edge e _i,j =(p,q) with l evenly spaced Steiner points on it, and the path $\delta_{T_{j}}(q, q_{1})$. We have obtained a new bottleneck Steiner path between s and t that satisfies conditions (i) and (ii) (for the subpath between p ₁ and q ₁).

We repeat this operation for the remaining pairs of consecutive terminals that violate one of the two conditions. Eventually, we obtain a bottleneck Steiner path $\delta_{G}^{*}(s,t,k)$ as required. □

Lemma 4.5

E ^∗ is of size O(k ² n) and can be computed in O(k ² nlogn+nlog² n) time.

Proof

Let G′ be a 2-spanner of G and let $\delta_{G'}^{*}(s,t,k)$ be a bottleneck Steiner path between s and t in G′ with at most k Steiner points and bottleneck λ′. By Corollary 4.3, λ′ can be computed in O(nlog² n) time. Put $\alpha=\frac{\lambda'}{2}$ and β=(k+1)λ′. We compute, according to Theorem 2.3, a weak (α,β)-pair decomposition $\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of P in O((β/α)² nlogn)=O(k ² nlogn) time. For each pair $(A,B)\in \mathcal{W}$, let (a,b) be a shortest edge connecting between a point a∈A and a point b∈B, and let E ^∗∗ be the set of these m edges. For a pair $(A,B)\in\mathcal{W}$, (a,b) can be computed in O((∥A∥+∥B∥)log(∥A∥)) time, by computing the Voronoi diagram of A together with a corresponding point location data structure and performing point location queries in the diagram with the points in B. Thus, since m=O(k ² n) and $\sum_{i=1}^{m}(\lVert A_{i}\rVert +\lVert B_{i}\rVert )=O (k^{2} n)$, |E ^∗∗|=O(k ² n) and it can be computed in time

$$\begin{aligned} \sum_{i=1}^{m}\bigl(\lVert A_i\rVert +\lVert B_i\rVert\bigr) \log{\bigl(\lVert A_i\rVert \bigr)}\le\log{n}\cdot\sum_{i=1}^{m}\bigl(\lVert A_i\rVert+\lVert B_i\rVert \bigr) = O \bigl(k^2 n\log n \bigr) . \end{aligned}$$

We now show that E ^∗⊆E ^∗∗. Recall that, for any two points p, q∈P, with λ′/2=α<|pq|≤β=(k+1)λ′, there exists a single pair $(A_{i},B_{i})\in\mathcal{W}$, such that p∈A _i and q∈B _i , or vice versa. Let V _i , V _j , i≠j, be any two subsets for which |e _i,j |=|(p,q)|≤(k+1)λ′. (Recall that e _i,j is the shortest edge between V _i and V _j and that |e _i,j |>λ′/2.) We need to show that e _i,j ∈E ^∗∗. There exists a single pair $(A_{l},B_{l})\in\mathcal{W}$, such that p∈A _l and q∈B _l . Since A _l (resp. B _l ) is contained in a grid cell of diagonal $\lambda '/(2\sqrt{2})$, the distance between any two points in A _l (resp. in B _l ) is less than $\frac{\lambda'}{2}$, and, therefore, A _l ⊆V _i and B _l ⊆V _j . This implies that e _i,j is also the shortest edge between A _l and B _l , and therefore e _i,j ∈E ^∗∗.

Finally, we obtain E ^∗ from E ^∗∗ as follows. We first compute the sets V ₁,V ₂,…, and, for each p∈P, we indicate the set V _i to which it belongs. Then, for each edge (a,b)∈E ^∗∗, such that a and b are in different sets V _i , V _j , we proceed as follows. If there already exists an edge in E ^∗ between V _i and V _j , then we replace it by (a,b) if and only if (a,b) is shorter. Otherwise, we add the edge (a,b) to E ^∗. This stage can be performed in O(k ² n+nlogn) time. □

We are now ready to present our algorithm. Given a set P of n terminals, two terminals s, t∈P, and a positive integer k, Algorithm 3 finds a Steiner path between s and t with at most k Steiner points and with bottleneck λ ^∗, where λ ^∗ is the optimum bottleneck. It first constructs the set $E^{*} \cup\mathcal{T}$, and then generates a search space of (k+1)|E ^∗| potential values that necessarily includes λ ^∗. Finally, it finds the value λ ^∗, by performing a binary search in the search space, using Algorithm 2 to decide whether, for a given value λ, there exists a path from s to t with at most k Steiner points and bottleneck at most λ. Once λ ^∗ is found, it is easy to produce the desired Steiner path.

Algorithm 3

EBSP(P,s,t,k)

Correctness

The correctness of the algorithm follows from the lemmas and text preceding it.

Complexity

A minimum spanning tree T can be computed in O(nlogn) time, and, by Lemma 4.5, E ^∗ is of size O(k ² n) and can be computed in O(k ² nlogn+nlog² n) time. Thus, the number of values in the search space S is O(k ³ n). Using Dijkstra’s algorithm [13], a shortest path between s and t in $G=(P,E^{*} \cup\mathcal{T})$ can be found in O(k ² n+nlogn) time, and, since Dijkstra’s algorithm is applied O(logn) times, the total running time of Algorithm 3 is O(k ³ n+k ² nlogn+nlog² n). Actually, a more careful analysis allows us to drop the term k ³ n from the running time of Algorithm 3. Observe that S can be represented implicitly by the (k+1)×|E ^∗| sorted matrix S={s _i,j }, where $s_{i,j} = \frac{e_{j}}{k-i+2}$ and e _j is the j-th shortest edge in E ^∗, and therefore selection in S can be performed in O(klogn) time [15].

The following theorem summarizes our main result.

Theorem 4.6

Given a set P of n terminals in the plane, two terminals s,t∈P, and a positive integer k, a bottleneck Steiner path between s and t with at most k Steiner points can be computed in O(k ² nlogn+nlog² n) time.

Remarks

(i) Note that Algorithm 3 runs in O(nlog² n) time for any constant k≥0, and in subquadratic time for k=o(n ^1/2). (ii) If we forbid edges between Steiner points in our path, then the problem can be solved in O(nlog² n) time, for any k≥0.

4.3 Solving Dual-EBSP

In the dual problem, we are given a set P of n terminals in the plane, two terminals s,t∈P, and a constant λ>0, and we must find a Steiner path between s and t with bottleneck at most λ, using as few Steiner points as possible. Let k ^∗ denote the minimum number of Steiner points needed to achieve bottleneck at most λ. We discuss three approaches for computing k ^∗.

As mentioned in Sect. 4.1, an O(|E|)=O(n ²)-time algorithm for Dual-EBSP can be derived immediately from Algorithm 1. The second approach is based on Algorithm 3. We search for k ^∗ in the sequence $1,2,\ldots,2^{ \lceil\log{k^{*}} \rceil }$, resolving comparisons by calls to Algorithm 3. This approach leads to an algorithm with running time O(logk ^∗⋅(k ^{∗ 2} nlogn+nlog² n)).

The third approach is based on geometric floor spanners (or, more accurately, on spanners for the weight function w(p,q)=⌈|pq|⌉−1), introduced in the next section (see also the remark at the end of the next section). For any ε>0, the (1+ε)-spanner of P (w.r.t. w) contains a path δ(s,t) between s and t, such that ∑ _e∈δ(s,t)(⌈|e|/λ⌉−1)≤(1+ε)⋅k ^∗. Moreover, the spanner can be computed in time O((1/ε ²)nlog² n). Therefore, by taking ε<1/k ^∗, we can obtain an optimal path between s and t.

A value smaller than 1/k ^∗ is found by bootstrapping, as follows. We first construct in O(nlog² n) time a (3/2)-spanner G′ of G. Let δ _G′(s,t) be the shortest path between s and t in G′ and let $k'=\sum_{e\in\delta_{G'}(s,t)}( \lceil|e|/\lambda \rceil- 1)$. Clearly, k ^∗≤k′≤3k ^∗/2. Next, we take ε=1/k′≤1/k ^∗ and construct in O(k′² nlog² n)=O(k ^{∗ 2} nlog² n) time a (1+1/k′)-spanner G″, of size O(k′² n)=O(k ^{∗ 2} n), that contains an optimal path between s and t. Finally, we apply the first approach above to compute k ^∗ in O(k ^{∗ 2} n+nlogn) time. The following theorem summarizes our result.

Theorem 4.7

Given a set P of n terminals in the plane, two terminals s, t∈P, and a constant λ, a Steiner path between s and t with bottleneck at most λ, using k ^∗ Steiner points, can be computed in O(k ^{∗ 2} nlog² n) time.

5 Floor Spanner

In this section we consider the problem of constructing a floor (1+ε)-spanner of a set P of n points in the plane. Let G=(P,E) be the complete graph over P with weight function w′(p,q)=⌊|pq|⌋. For two points p, q∈P, let δ _G (p,q) denote the shortest path between p and q in G (under w′), where the weight of a path is, as usual, the sum of the weights of the edges along the path. Notice that under w′, the shortest path between two points is not necessarily the edge between them.

Definition 5.1

Let P be a set of n points in the plane and let t>1 be a constant. A graph G′=(P,E′) is a floor t-spanner of P if, for each pair p, q∈P, w′(δ _G′(p,q))≤t⋅w′(δ _G (p,q)).³

We now describe how to construct, in O(nlog² n) time, a floor t-spanner of P, for any constant t>1. Put α=1 and $\beta =\frac{t}{(\gamma t-1)\cos{\frac{\theta}{2}}}$, where γ=(cosθ−sinθ) and θ is an appropriate constant to be specified later. We first compute a weak (α,β)-pair decomposition, $\mathcal{W}$, of P. Next, we compute from $\mathcal {W}$ the set of edges E ^∗∗, as in the proof of Lemma 4.5. Let E ₁ be the set of edges containing E ^∗∗ and the edges of a minimum spanning tree of P, $\mathcal{MST}(P)$. We now construct a second set of edges, E ₂.

The construction of E ₂ is similar to that of a Θ-graph [12, 20]. For each point p∈P, partition the plane into k=⌈2π/θ⌉ cones C _p,1,C _p,2,…,C _p,k , with apex at p and angle at most θ. Consider a cone C _p,i . Let l _p,i be the ray emanating from p and dividing the angle of C _p,i into two halves, and let P _p,i be the set of points in P∩C _p,i , for which the distance between their orthogonal projection onto l _p,i and p is greater than $\frac{t}{\gamma t-1}$. For each cone C _p,i , we add to E ₂ an edge between p and the point q in P _p,i whose orthogonal projection onto l _p,i is closest to p. We now show that G′=(P,E ₁∪E ₂) is a floor t-spanner of P.

Lemma 5.2

If θ is chosen so that $\gamma= \cos{\theta}-\sin{\theta} > \frac{1}{t}$, then G′ is a floor t-spanner of P.

Proof

To prove the lemma it suffices to show that, for any two points p, q∈P, w′(δ _G′(p,q))≤t⋅⌊|pq|⌋. We show this by induction on the rank of the distance |pq| in the sorted sequence of distances in P.

Base case: If p, q are the closest pair in P, then (p,q) is an edge of the minimum spanning tree of P, and therefore also of E ₁.

Induction step: If p, q are not the closest pair, then we distinguish between two cases. Assume first that |pq|≤β. If p, q lie in the same grid cell, then all edges of the path in $\mathcal{MST}(P)$ between p and q are of length at most $|pq| \le\alpha/\sqrt{2} < 1$, and therefore, since $\mathcal{MST}(P) \subseteq E_{1}$, w′(δ _G′(p,q))=0. If p, q lie in different grid cells, then there is a pair $(A,B) \in\mathcal{W}$ such that p∈A and q∈B. If (p,q)∈E ₁, then we are done. Otherwise, there is an edge (a,b)∈E ₁ such that a∈A, b∈B and |ab|≤|pq|. Since |pa|, $|bq| \le\alpha/\sqrt{2} < 1$, w′(δ _G′(p,a))=w′(δ _G′(b,q))=0, and therefore

$$ w' \bigl(\delta_{G'}(p,q) \bigr) \le w' \bigl( \delta_{G'}(p,a) \bigr) + \bigl\lfloor |ab| \bigr\rfloor + w' \bigl( \delta_{G'}(b,q) \bigr) \le\bigl\lfloor |pq| \bigr\rfloor . $$

Assume now that $|pq| > \beta= \frac{t}{(\gamma t-1)\cos{\frac {\theta }{2}}}$, and assume that our claim is true for all distances of rank less than that of |pq|. Let C _p,i be the cone (with apex at p) containing q. Notice that, since $|pq| > \frac{t}{(\gamma t-1)\cos {\frac{\theta}{2}}}$, the distance between p and the orthogonal projection of q onto l _p,i , denoted d _q , is greater than $\frac {t}{\gamma t-1}$. Hence, the point q was considered during the construction of E ₂. If (p,q)∈E ₂, then we are done; otherwise, there is a point q′ in C _p,i such that (p,q′)∈E ₂ and $\frac{t}{\gamma t-1} < d_{q'} \le d_{q}$. Therefore,

$$ w' \bigl(\delta_{G'}(p,q) \bigr) \le \bigl\lfloor |pq'| \bigr\rfloor + w' \bigl(\delta _{G'} \bigl(q',q \bigr) \bigr) . $$

By Lemma 4.1.4 in [26], we have |q′q|≤|pq|−(cosθ−sinθ)⋅|pq′|=|pq|−γ⋅|pq′|. Since γ>0, we conclude that |q′q|<|pq| and, therefore, we may apply the induction hypothesis to |q′q|, that is,

$$\begin{aligned} w' \bigl(\delta_{G'}(p,q) \bigr)&\le \bigl\lfloor \big|pq'\big| \bigr\rfloor + t\cdot \bigl\lfloor \big|q'q\big| \bigr\rfloor \\ &\le \bigl\lfloor \big|pq'\big| \bigr\rfloor + t\cdot \bigl\lfloor |pq|- \gamma \cdot\big|pq'\big| \bigr\rfloor \\ &\le\big|pq'\big| + t\cdot|pq|-t\gamma\cdot\big|pq'\big| \\ &\le t\cdot|pq| - (t\gamma-1)\cdot\big|pq'\big| . \end{aligned}$$

Finally, since $\gamma> \frac{1}{t}$ and $|pq'| > \frac{t}{\gamma t-1}$, we obtain

$$\begin{aligned} w' \bigl(\delta_{G'}(p,q) \bigr) &\le t\cdot|pq| - (t \gamma-1)\cdot\frac{t}{\gamma t-1} \\ &\le t\cdot\bigl(|pq|-1\bigr) \le t\cdot\bigl\lfloor |pq| \bigr\rfloor . \end{aligned}$$

This completes the proof of the lemma. □

Lemma 5.3

Let t=1+ε, where 0<ε≤1/2. Then, for θ=ε/4, G′ is a floor t-spanner of P with O(n/ε ²) edges. Moreover, G′ can be constructed in O((1/ε ²)nlog² n) time.

Proof

Since 0<θ≤1/8, we have sinθ<θ and 1−cosθ<θ. Hence,

$$\begin{aligned} \gamma=\cos{\theta}-\sin{\theta} > 1- 2\theta= 1-\frac {\varepsilon }{2}> \frac{1}{t} , \end{aligned}$$

and, by Lemma 5.2, G′ is a floor t-spanner of P. We now bound the size of G′.

The size of E ₂ is O(n/θ)=O(n/ε). As for E ₁, $\mathcal{MST}(P)$ is of size O(n) and E ^∗∗ is of size O((β/α)² n). Hence, E ₁ is of size O((β/α)² n). Since α=1 and

$$\begin{aligned} \beta= \frac{t}{(\gamma t - 1)\cos{\frac{\theta}{2}}} < \frac {2}{((1-\frac{\varepsilon}{2}) (1+\varepsilon) - 1)\cos{\frac {\varepsilon}{8}}} < \frac{4}{\cos{\frac{1}{16}}} \cdot \frac {1}{\varepsilon(1-\varepsilon)} < \frac{8}{\cos{\frac{1}{16}}} \cdot\frac{1}{\varepsilon} \,, \end{aligned}$$

the size of E ₁ is O(n/ε ²).

Finally, according to the proof of Lemma 4.5, E ^∗∗ can be constructed in O((β/α)² nlogn)=O((1/ε ²)nlogn) time. Moreover, a minimum spanning tree of P can be constructed in O(nlogn) time [14]. The set E ₂ can be constructed in O((1/ε)nlog² n) time, by a slight modification of the O((1/θ)nlogn)-time algorithm for computing the Θ-graph (see [26]). Therefore, G′ can be constructed in O((1/ε ²)nlog² n) time, as claimed. □

By combining Lemma 5.2 and Lemma 5.3, we obtain the following theorem.

Theorem 5.4

For any set P of n points in the plane and for any ε>0, a floor (1+ε)-spanner of P with O(n/ε ²) edges can be constructed in O((1/ε ²)nlog² n) time.

Remark

Notice that sparse ceiling (1+ε)-spanners do not exist. For example, take n points in a disk of diameter 1. Then, for any 0<ε<1, any (1+ε)-spanner will have Ω(n ²) edges. However, for the function w, defined as w(p,q)=⌈|pq|⌉−1, one can adapt our proof above to show that there exists a sparse (1+ε)-spanner of P, even though w(p,q)≠w′(p,q).

6 Distance Selection

In this section we consider the distance selection problem. Given a set P of n points and an integer parameter k, $1 \leq k \leq {n}\choose{2}$, we wish to compute the k-th smallest Euclidean distance among the $n\choose{2}$ distances determined by pairs of points in P. Let $d_{1} \leq d_{2} \leq\cdots\leq d_{n\choose{2}}$ be the distances determined by the points in P. The best deterministic algorithm to date for finding d _k runs in time O(n ^4/3log^2+ε n) (see Katz and Sharir [19]), and the currently best deterministic algorithm for computing a one-sided approximation of d _k (i.e., a value x such that d _k ≤x≤(1+ε)d _k ) runs in time O(nlog³ n+n/ε ²) (see Bespamyatnikh and Segal [5]). The latter authors also presented an algorithm for computing a two-sided approximation of d _k (i.e., a value x such that (1−ε)d _k ≤x≤(1+ε)d _k ) that runs in O(nlogn+n/ε ²) time. In what follows we show how to improve the running time of the algorithm for computing a one-sided approximation of d _k , using a weak (α,β)-pair decomposition.

We proceed as follows. First, we compute a weak (α,β)-pair decomposition $\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{l},B_{l})\}$ of P, for appropriate values of α and β (see below). Then, for each pair $(A_{i},B_{i}) \in\mathcal{W}$, we compute (i) the maximal distance M _i defined by a point from A _i and a point from B _i , (ii) the minimal distance m _i defined by a point from A _i and a point from B _i , and (iii) the number of distances δ _i defined by the pair (A _i ,B _i ), which is δ _i =|A _i |⋅|B _i |. Observe that the values m _i and M _i , i=1,…,l, can be computed in total time O(nlogn), using the nearest and farthest Voronoi diagrams of A _i , as described in Lemma 4.5. In order to guarantee that the distances defined by a pair (A _i ,B _i ) are roughly the same, i.e., up to a factor of 1+ε of each other, we need to set the values of α and β such that $\frac{\sqrt{2}\alpha+ \beta}{\beta} \leq1+\varepsilon$. We also want to ensure that all the distances defined by the points within a single grid cell of the decomposition are strictly smaller than d _k , so we require that $\alpha/\sqrt{2} < d_{k}$. Ideally, we would set β=d _k ; however, d _k is not known. Instead, let x be a two-sided approximation of d _k , obtained in O(nlogn+n/ε ²) time, by applying the algorithm mentioned above. We set $\beta= \frac{x}{1-\varepsilon} \ge d_{k}$ and $\alpha= \frac{\varepsilon}{\sqrt{2}}\cdot\frac{x}{1-\varepsilon}$. Notice that $M_{i}/m_{i} \le\frac{\sqrt{2}\alpha+ \beta}{\beta} = 1+\varepsilon$, and that $\alpha/\sqrt{2} < \frac{x}{1+\varepsilon} \le d_{k}$, assuming ε≤1/2. Moreover, $\beta/\alpha= \sqrt{2}/\varepsilon$.

Let r be the number of distances defined by pairs of points residing in the same grid cell, over all cells of the decomposition. Our choice of α ensures that k>r. Let us assume, without loss of generality, that m ₁≤m ₂≤⋯≤m _l . We find the smallest integer j such that $r+\sum_{i=1}^{j}\delta_{i} \geq k$, and set $M=\max_{i=1}^{j} M_{i}$. We claim that M is a one-sided approximation of d _k , i.e., d _k ≤M≤(1+ε)d _k . Clearly, d _k ≤M, since M is the maximum distance among the distances defined by the pairs (A ₁,B ₁),…,(A _j ,B _j ) and each of the additional r distances is strictly less than d _k , and the total number of all these distances is at least k. On the other hand, let δ _l+1 be the number of distances defined by pairs of points residing in different grid cells that are not represented in $\mathcal{W}$. Then, by definition, all these distances are greater than β and therefore strictly greater than d _k . Consider the sum of δ _l+1 and the number of distances defined by the pairs (A _j ,B _j ),…,(A _l ,B _l ). This sum is equal to ${n\choose{2}} - \sum_{i=1}^{j-1}\delta_{i} - r$, and therefore is strictly greater than ${n\choose{2}} - k$. We now establish that m _j ≤d _k . Clearly, m _j is the minimum distance among the distances defined by the pairs (A _j ,B _j ),…,(A _l ,B _l ). Also, m _j <m _l+1, where m _l+1 is the minimum distance among the distances counted by δ _l+1, since otherwise there are more than ${n\choose{2}} - k$ distances that are strictly greater than d _k , which is impossible. Now, since m _j is the minimum distance among a set of more than ${n\choose{2}} - k$ distances, it follows that m _j ≤d _k . To conclude, let t, 1≤t≤j, be an index such that M=M _t ; then, by our choice of α and β, we get that M=M _t ≤(1+ε)m _t ≤(1+ε)m _j ≤(1+ε)d _k . The following theorem summarizes the result of this section.

Theorem 6.1

For any set P of n points in the plane, for any integer parameter k, 1≤k≤ $n\choose{2}$, and for any 0<ε≤1/2, one can compute a one-sided approximation of d _k (i.e., of the k’th smallest Euclidean distance among the distances determined by pairs of points in P) in O((1/ε ²)nlogn) time.

7 Concluding Remarks

In this paper, we studied the Euclidean bottleneck Steiner path problem and its dual version, and presented efficient solutions for both problems. Our solutions are based on two new geometric structures, namely, a (weak) (α,β)-pair decomposition of a planar point set P and a floor (1+ε)-spanner of P (where the former is used in the construction of the latter). We also used an (α,β)-pair decomposition of P to obtain a strong hop-sensitive spanner and to improve the running time of the algorithm of Bespamyatnikh and Segal [5] for computing a one-sided approximation for planar distance selection. It would be interesting to see additional applications of (α,β)-pair decomposition.