首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号