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.Work on this paper by this author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, the IBM Corporation, and from the U.S.-Israel Binational Science Foundation.Work on this paper by this author has been supported by National Science Foundation Grant DCR-86-05962. |
| |
| Keywords: | Triangulation Simple polygon Visibility Shortest paths Ray shooting Computational geometry |
| 本文献已被 SpringerLink 等数据库收录！ |
|
