Shortest path solves edge-to-edge visibility in a polygon

Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


Given a simple polygon P = (p1, p2, ..., pn) consisting of n edges ei = [pipi+1], i = 1,2, ..., n, two edges ei and ej are said to be visible if there exists a point χε{lunate}ei and a point yε{lunate}ej such that the line segment [χ y] lies in P. An edge-to-edge visibility query asks for whether a specified pair of edges of P is visible. It is shown that with O(n log n) preprocessing of P, an edge-to-edge visibility query can be answered in O(n) time. The algorithm also reports a line-of-sight if the answer is in the affirmative.

Original languageEnglish (US)
Pages (from-to)165-170
Number of pages6
JournalPattern Recognition Letters
Issue number3
StatePublished - Jul 1986


  • Weak-visibility
  • computational geometry
  • edge-visibility graph
  • geodesic distance
  • graphics
  • image processing
  • polygon triangulation
  • shortest path

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Shortest path solves edge-to-edge visibility in a polygon'. Together they form a unique fingerprint.

Cite this