Determining sector visibility of a polygon

B. Bhattacharya, D. G. Kirkpatrick, G. T. Toussaint

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

Abstract

We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width u. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are θ(n) when γ < φ or γ = 2φr, but require ω(n log n) time (at least), when φ < u < 2φ.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th Annual Symposium on Computational Geometry, SCG 1989
PublisherAssociation for Computing Machinery
Pages247-254
Number of pages8
ISBN (Electronic)0897913183
DOIs
StatePublished - Jun 5 1989
Event5th Annual Symposium on Computational Geometry, SCG 1989 - Saarbruchen, Germany
Duration: Jun 5 1989Jun 7 1989

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
VolumePart F130124

Other

Other5th Annual Symposium on Computational Geometry, SCG 1989
Country/TerritoryGermany
CitySaarbruchen
Period6/5/896/7/89

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Determining sector visibility of a polygon'. Together they form a unique fingerprint.

Cite this