Visibility between two edges of a simple polygon

David Avis, Teren Gum, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simple n-vertex polygon. Four natural definitions of edge-to-edge visibility are proposed. There exist O(nlog n) algorithms and complicated O(nlog log n) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.

Original languageEnglish (US)
Pages (from-to)342-357
Number of pages16
JournalThe Visual Computer
Issue number6
StatePublished - Dec 1986


  • Algorithms
  • Computational geometry
  • Convex hull
  • Geometric complexity
  • Graphics
  • Hidden line problems
  • Jordan sorting
  • Monotone polygons
  • Polygon
  • Visibility
  • Weak visibility

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Visibility between two edges of a simple polygon'. Together they form a unique fingerprint.

Cite this