Visibility and intersection problems in plane geometry

Bernard Chazelle, Leonidas J. Guibas

Research output: Contribution to journalArticlepeer-review

141 Scopus citations

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 languageEnglish (US)
Pages (from-to)551-581
Number of pages31
JournalDiscrete & Computational Geometry
Volume4
Issue number1
DOIs
StatePublished - Dec 1989
Externally publishedYes

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