the euclidean bottleneck steiner path problem
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(n log 2 n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. [Hou10], who gave an O(n 2 log n)-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 W={(A 1 ,B 1 ),...,(A m ,B m )} of pairs of subsets of P, satisfying: (i) For each pair (A i ,B i ) ? W, the radius of the minimum enclosing circle of A i (resp. B i ) is at most ?, and (ii) For any p,q ? P, such that |pq| ? ?, there exists a single pair (A i ,B i ) ? 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 n log n). Finally, for the complete graph with vertex set P and weight function w(p,q) = ?|pq|?, we construct a (1+?)-spanner of size O(n/? 4 ) in time O((1/? 4 )n log 2 n), even though w is not a metric.
geometric optimization steiner points bottleneck path geometric networks pair decomposition geometric spanners