An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge

Research output: Contribution to journalArticle

Abstract

In many computer applications areas such as graphics, automated cartography, image processing, and robotics the notion of visibility among objects modeled as polygons is a recurring theme. This paper is concerned with the visibility of a simple polygon from one of its edges. Three natural definitions of the visibility of a polygon from an edge presented. The following computational problem is considered. Given an n -sided simple polygon, is the polygon visible from a specified edge? An O(n), and thus optimal, algorithm is exhibited for determining edge visibility under any of the three definitions. The paper closes with an interesting characterization of visibility and some open problems in this area.

Original languageEnglish (US)
Pages (from-to)910-914
Number of pages5
JournalIEEE Transactions on Computers
VolumeC-30
Issue number12
DOIs
StatePublished - Dec 1981

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge'. Together they form a unique fingerprint.

  • Cite this