### 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 1 1989 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Visibility and intersection problems in plane geometry'. Together they form a unique fingerprint.

## Cite this

Chazelle, B., & Guibas, L. J. (1989). Visibility and intersection problems in plane geometry.

*Discrete & Computational Geometry*,*4*(1), 551-581. https://doi.org/10.1007/BF02187747