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 O(n log n)-time algorithm for computing the illuminated subpolygon of P from a luminous side, and an O(log n)-time 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 O(n log n) and space O(n). The two main tools in attacking these problems are geometric duality on the two-sided plane and fractional cascading.
Original language | English (US) |
---|---|
Pages (from-to) | 551-581 |
Number of pages | 31 |
Journal | Discrete & Computational Geometry |
Volume | 4 |
Issue number | 1 |
DOIs | |
State | Published - Dec 1989 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics