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.
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.
L. Gewali, and R. Lombardo,"Watchman routes for a pair of convex polygons",Lecture Notes in Pure and Applied Mathematics, 144, 287-300, (1994).
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 |