@inproceedings{514f331ef449438d92b5f29fd444f0f1,
title = "Optimal shortest path and minimum-link path queries in the presence of obstacles",
abstract = "We present efficient algorithms for shortest-path and minimum-link- path queries between two convex polygons inside a simple polygon, which acts as an obstacle to be avoided. We also extend our results to the dynamic case, and give a unified data structure that supports both queries for convex polygons in the same region of a connected planar subdivision. Performing shortest-path queries is a variation of the well studied separation problem, which has not been efficiently solved before in the presence of obstacles. Also, it was not previously known how to perform minimum-link-path queries in a dynamic environment, even for two-point queries.",
author = "Chiang, {Yi Jen} and Roberto Tamassia",
note = "Funding Information: Research supported in part by the National Science Foundation under grant CCR- 9007851, by the U.S. Army Research Office under grants DAAL03-91-G-0035 and DAAH04-93-0134, and by the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-91-J-4052, ARPA order 8225. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 2nd Annual European Symposium on Algorithms, ESA 1994 ; Conference date: 26-09-1994 Through 28-09-1994",
year = "1994",
doi = "10.1007/bfb0049414",
language = "English (US)",
isbn = "9783540584346",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "266--277",
editor = "{van Leeuwen}, Jan",
booktitle = "Algorithms - ESA'94 - 2nd Annual European Symposium, Proceedings",
}