The Euclidean Bottleneck Steiner Path Problem and Other Applications of (alpha,beta)-Pair Decomposition Academic Article uri icon


  • 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(nlog2 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 2logn)-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((β/α)3 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/ε 2) edges in time O((1/ε 2)nlog2 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/ε 2)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.

publication date

  • January 1, 2014