Approximating Geometric Bottleneck Shortest Paths

In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: Given two points p and q of S and a real number L, compute (or approximate) a shortest path in the subgraph of the complete graph on S consisting of all edges whose length is less than or equal to L. We present ecient algorithms for answering several query problems of this type. Our solutions are based on minimum spanning trees, spanners, the Delaunay triangulation, and planar separators