Computing Visibility Properties of Polygons

Godfried T. Toussaint

Research output: Chapter in Book/Report/Conference proceedingChapter


In many pattern recognition problems the objects of interest are represented as polygons. For some applications such as pattern matching the shape of the polygons is successfully measured in terms of the visibility relations between the edges. In this paper we survey some recent results in computational geometry that allow efficient computation of visibility properties between edges of a simple polygon as well as more general visibility relations. In particular, four natural definitions of edge-to-edge visibility are considered and a linear-time, and thus optimal, algorithm is discussed to determine edge-to-edge visibility under any of the four definitions. Furthermore, an O(n log log n) time algorithm is reviewed for determining that region of an n-gon P that is weakly visible from a specified edge of P (the strong hidden-line problem). The algorithm combines results from visibility and geodesic paths with the recent polygon triangulation algorithm of Tarjan and Van Wyk [42]. We also discuss the problem of determining whether a polygon is visible from a specified edge. In particular three natural definitions of edge-visibility of polygons are considered and new optimal algorithms are proposed for testing visibility from a specified edge under any of the three definitions.

Original languageEnglish (US)
Title of host publicationMachine Intelligence and Pattern Recognition
Number of pages20
StatePublished - Jan 1 1988

Publication series

NameMachine Intelligence and Pattern Recognition
ISSN (Print)0923-0459

ASJC Scopus subject areas

  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Computing Visibility Properties of Polygons'. Together they form a unique fingerprint.

Cite this