Bernard Chazelle
ABSTRACT
We develop new data structures for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple Ο(n log n) algorithm for computing the illuminated subpolygon of P from a luminous side, and an Ο(log n) algorithm for determining which side of P is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing on P which takes time Ο(n log n) and space Ο(n). Our main new tool in attacking these problems is geometric duality on the two-sided plane.
- [1] Chazelle, B. A theorem on polygon cutting with applications , Proc. 23rd Annual FOCS Symp., 339-349, 1982.Google Scholar
Digital Library
- [2] Chazelle, B. Computing on a free tree via complexity preserving mappings, Proc. 25th Annual FOCS Symp., 358- 368, 1984.Google ScholarDigital Library
- [3] Chazelle, B., and Guibas, L.J., Fractional Cascading: A data structuring technique with geometric applications, Efficient Algorithms workshop, Oberwalfach, W. Germany, 1984. To appear in the Proceedings of the 1985 ICALP, Nafplion, Greece.Google Scholar
- [4] El Gindy, H.A. An efficient algorithm for computing the weak visibility polygon from an edge in simple polygons, unpublished manuscript, McGill University, 1984.Google Scholar
- [5] Guibas, L., Ramshaw, L., and Stolfi, J. A kinetic framework for computational geometry, Proc. 24th Annual FOCS Symp., pp. 100-111, 1983.Google ScholarDigital Library
- [6] Lee, D.T., and Lin, A., Computing the visibility polygon from an edge, unpublished manuscript, Northwestern Univ., 1984.Google Scholar
- [7] Edelsbrunner, H., Guibas, L., and Stolfi, J., Optimal point location in monotone subdivisions. DEC/SRC Technical Report #2, 1984.Google Scholar
Index Terms
- Visibility and intersectin problems in plane geometry
Recommendations
Linear time algorithms for visibility and shortest path problems inside simple polygons
SCG '86: Proceedings of the second annual symposium on Computational geometryWe present linear time algorithms for solving the following problems involving a simple planar polygon P: (i) Computing the collection of all shortest paths inside P from a given source vertex s to all the other vertices of P; (ii) Computing the ...
Visibility and intersection problems in plane geometry
We develop new data structures for solving various visibility and intersection problems about a simple polygonP onn vertices. Among our results are a simpleO(n logn)-time algorithm for computing the illuminated subpolygon ofP from a luminous side, and ...
An Optimal Algorithm for Computing Visibility in the Plane
The authors give an algorithm to compute the visibility polygon from a point among a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices. Our algorithm uses $O(n)$ space and runs in optimal time $\Theta(n+h\log h)$, improving ...
Comments