Optimal link path queries in a simple polygon
Esther M. Arkin, Joseph S. B. Mitchell, Subhash Suri · Symposium on Discrete Algorithms · 1992
We develop a data structure for answering link distance queries between two arbitrary points in a simple polygon. The data structure requires O(n3) time and space for its construction and answers link distance queries in O(log n) time. Our result extends to link distance queries between pairs of segments or polygons. We also propose a simpler data structure for computing a link distance approximately, where the error is bounded by a small additive constant. Finally, we also present a scheme for approximating the link and the shortest path distance simultaneously.