Visibility and intersection problems in plane geometry

Bernard Chazelle, Leonidas J. Guibas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

52 Scopus citations

Abstract

We develop new data structure! for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple 0(nlog n) algorithm for computing the illuminated subpolygon of P from a luminous side, and an 0(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 take time 0(n log n) and space 0(n). Our main new tool in attacking these problems is geometric duality on the two-sided plane.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages135-146
Number of pages12
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Externally publishedYes
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

NameProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/7/85

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Geometry and Topology

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

Cite this