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 is an element of 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 Hon et al. [11], 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 + epsilon)-spanner of P. For real numbers beta > alpha > 0, an (alpha, beta)-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) is an element of W, the radius of the minimum enclosing circle of A(i) (resp. B-i) is at most a, and (ii) For any p, q is an element of P, such that vertical bar pq vertical bar <= beta, there exists a single pair (A(i), B-i) is an element of W, such that p is an element of A(i). and q is an element of 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). Finally, for the complete graph with vertex set P and weight function w(p, q) = left perpendicular vertical bar pq vertical bar right perpendicular, we construct a (1 + epsilon)-spanner of size O(n/epsilon(4)) in time O((1/epsilon(4))n log(2) n), even though to is not a metric.