|
|||||
|
|
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons |
|
| Authors: | Leonidas Guibas John Hershberger Daniel Leven Micha Sharir Robert E. Tarjan |
| Affiliation: | 1. Computer Science Department, Stanford University, 94305, Stanford, CA, USA 2. DEC/SRC, 130 Lytton Avenue, 94301, Palo Alto, CA, USA 3. School of Mathematical Sciences, Tel-Aviv University, 69978, Tel Aviv, Israel 4. Courant Institute of Mathematical Sciences, New York University, 10012, New York, NY, USA 5. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA 6. AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA |
| Abstract: | Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |
