Watchman Problems

Table of contents

The shortest watchman route with no starting point

A closed walk W starting and ending at a starting point s such that every point in P is visible from some point in Wis called a watchman route with a starting point. Chin and Ntafos obtained an algorithm to find a watchman route of minimum length for polygons with n vertices in O(n2) time.

A watchman route starting at S.

The following problem is due to Chin and Ntafos:

Problem: Find, if possible, an efficient algorithm to find the shortest watchman route without a starting point for simple polygons.

  1. W. P. Chin, and S. Ntafos,"Watchman routes in simple polygons" Discrete and Computational Geometry, 6, 9-31, (1991).

Optimal watchman routes to guard the exterior of two convex polygons

The following problem is due to Gewali and Ntafos:

Problem: Is it possible to find a subquadratic time algorithm to calculate the shortest watchman route to guard the exterior of two disjoint convex polygons such that their boundaries contain n vertices?

There is an O(n2) time algorithm due to Gewali and Ntafos [2]. In an earlier paper, Gewali and Lombardo [1] obtained an O(n3) time algorithm. According to Gewali, one of the main problems is that the optimal solution does not need to touch the boundary of the polygons to be guarded; see the following figure.

A watchman route (blue) that does not touch the polygons to be guarded (red).

  1. L. Gewali, and R. Lombardo,"Watchman routes for a pair of convex polygons",Lecture Notes in Pure and Applied Mathematics, 144, 287-300, (1994).

  2. L. Gewali and S. Ntafos,"Watchman routes in the presence of a pair of convex polygons", Proc. Seventh Canadian Conference on Computational Geometry, 127-132, (1995).

A la página principal de problemas abiertos . A mi página.

Jorge Urrutia,
Instituto de Matemáticas,
Universidad Nacional Autónoma de México
urrutia@matem.unam.mx
School of Information Technology and Engineering
University of Ottawa,
jorge@site.uottawa.ca

A la página del Instituto de Matemáticas