Article ID: | iaor20002983 |
Country: | United States |
Volume: | 28 |
Issue: | 6 |
Start Page Number: | 2215 |
End Page Number: | 2256 |
Publication Date: | Jun 1999 |
Journal: | SIAM Journal On Computing |
Authors: | Suri Subhash, Hershberger John |
We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time