TY - GEN
T1 - Optimal link path queries in a simple polygon
AU - Arkin, Esther M.
AU - Mitchell, Joseph S.B.
AU - Suri, Subhash
PY - 1992/9/1
Y1 - 1992/9/1
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/0041802039
M3 - Conference contribution
AN - SCOPUS:0041802039
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 269
EP - 279
BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
PB - Association for Computing Machinery
T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
Y2 - 27 January 1992 through 29 January 1992
ER -