Summary: 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\in 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(n\log ^{2} n)\)-time algorithm that computes an optimal solution, for any constant \(k\). This problem was previously studied by Y. T. Hou, C. M. Chen and B. Jeng in [Wirel. Netw. 16, No. 4, 1033–1043 (2010)], who gave an \(O(n ^{2} \log n)\)-time algorithm. We also study the dual version of the problem, where a value \(\lambda >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 \(\lambda \).
Our algorithms are based on two new geometric structures that we develop – an \((\alpha ,\beta )\)-pair decomposition of \(P\) and a floor \((1+\varepsilon )\)-spanner of \(P\). For real numbers \(\beta >\alpha >0\), an \((\alpha ,\beta )\)-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 \(\alpha \), and (ii) for any \(p, q\in P\), such that \(|pq|\leq \beta \), there exists a single pair \((A_{i},B_{i}) \in\mathcal{W}\), such that \(p\in A _{i }\) and \(q\in B _{i }\), or vice versa. We construct (a compact representation of) an \((\alpha ,\beta )\)-pair decomposition of \(P\) in time \(O((\beta /\alpha )^{3} n \log n)\). In some applications, a simpler (though weaker) grid-based version of an \((\alpha ,\beta )\)-pair decomposition of \(P\) is sufficient. We call this version a weak \((\alpha ,\beta )\)-pair decomposition of \(P\).
For \(\varepsilon >0\), a floor \((1+\varepsilon )\)-spanner of \(P\) is a \((1+\varepsilon )\)-spanner of the complete graph over \(P\) with weight function \(w(p,q)=\lfloor |pq|\rfloor \). We construct such a spanner with \(O(n/\varepsilon ^{2})\) edges in time \(O((1/\varepsilon ^{2})n\log ^{2} n)\), even though \(w\) is not a metric.
Finally, we present two additional applications of an \((\alpha ,\beta )\)-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/\varepsilon ^{2})n \log n)\)-time algorithm for computing a one-sided approximation for distance selection (i.e., given \(k, 1 \leq k \leq{n \choose2}\), find the \(k\)’th smallest Euclidean distance induced by \(P\)), significantly improving the running time of the algorithm of S. Bespamyatnikh and M. Segal [Algorithmica 33, No. 2, 263–269 (2002; Zbl 1052.68145)].