Determining sector visibility of a polygon

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

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


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
Number of pages8
ISBN (Electronic)0897913183
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


Other5th Annual Symposium on Computational Geometry, SCG 1989

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


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

Cite this