Visibility-polygon search and euclidean shortest paths
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 155-164
- https://doi.org/10.1109/sfcs.1985.65
Abstract
Consider a collection of disjoint polygons in the plane containing a total of n edges. We show how to build, in O(n2) time and space, a data structure from which in O(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed in O(n2) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed in O(n2) time, improving earlier O(n2 log n) results.Keywords
This publication has 13 references indexed in Scilit:
- Filtering Search: A New Approach to Query-AnsweringSIAM Journal on Computing, 1986
- An algorithm for shortest-path motion in three dimensionsInformation Processing Letters, 1985
- Constructing the visibility graph for n-line segments in O(n2) timeInformation Processing Letters, 1985
- The power of geometric dualityBIT Numerical Mathematics, 1985
- Euclidean shortest paths in the presence of rectilinear barriersNetworks, 1984
- On shortest paths in polyhedral spacesPublished by Association for Computing Machinery (ACM) ,1984
- Visibility of a simple polygonComputer Vision, Graphics, and Image Processing, 1983
- A linear algorithm for computing the visibility polygon from a pointJournal of Algorithms, 1981
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- Triangulating a simple polygonInformation Processing Letters, 1978