Back to Search
Start Over
Query-point visibility constrained shortest paths in simple polygons
- Source :
-
Theoretical Computer Science . Dec2007, Vol. 389 Issue 1/2, p1-11. 11p. - Publication Year :
- 2007
-
Abstract
- Abstract: In this paper, we study the problem of finding the shortest path between two points inside a simple polygon such that there is at least one point on the path from which a query point is visible. We provide an algorithm which preprocesses the input in time and space and provides logarithmic query time. The input polygon has vertices and is a parameter dependent on the input polygon which is in the worst case but is much smaller for most polygons. The preprocessing algorithm sweeps an angular interval around every reflex vertex of the polygon to store the optimal contact points between the shortest paths and the windows separating the visibility polygons of the query points from the source and the destination. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*POLYGONS
*COMPUTER science
*SYSTEMS design
*INFORMATION science
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 389
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 27641355
- Full Text :
- https://doi.org/10.1016/j.tcs.2007.07.003