External Watchman Routes

Abstract

We consider the problem of finding a shortest watchman route from which the exterior of a polygon is visible (external watchman route). We present an O(n to the 4th power loglogn) algorithm to find shortest external watchman routes for simple polygons by transforming the external watchman route problem to a set of internal watchman route problems. Also, we present faster external watchman route algorithms for special cases. These include optimal O(n) algorithms for convex, monotone, star and spiral polygons and an O(n loglogn) algorithm for rectilinear polygons. Keywords: Visibility, Art gallery problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1990
Accession Number
ADA226065

Entities

People

  • Laxmi P. Gewali
  • Simeon Ntafos

Organizations

  • University of Nevada, Las Vegas

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Boundaries
  • Computer Science
  • Computers
  • Electrical Engineering
  • Geometry
  • Inequalities
  • Information Processing
  • Mathematics
  • Motion Planning
  • Pattern Recognition
  • Polygons
  • Right Angles
  • Separators
  • Visibility

Readers

  • Graph Algorithms and Convex Optimization.
  • Marine Ecotoxicology
  • Nanocomposite Materials Science