Approximation Algorithms for Anchored Multiwatchman Routes

Authors

  • Joseph S.B. Mitchell Stony Brook University
  • Linh Nguyen Stony Brook University

DOI:

https://doi.org/10.57717/cgt.v4i1.71

Abstract

We study some variants of the k-Watchman Routes problem, the cooperative version of the classic Watchman Route problem in a simple polygon. The k watchmen may be required to see the whole polygon, or some pre-determined quota of area within the polygon, and we want to minimize the maximum length traveled by any watchman. While the single-watchman (k = 1$ version of the problem has received considerable attention and is relatively well understood, much less is known about the multiple watchmen (k >1) variant(s).

We provide the first tight approximability results for the anchored k-Watchman Routes problem in a simple polygon, assuming k is fixed, by a fully-polynomial time approximation scheme. The basis for the FPTAS is provided by an exact dynamic programming algorithm. If k varies (i.e., it is part of the input), we give constant-factor approximations.

Downloads

Published

2025-08-03

How to Cite

Mitchell, J. S., & Nguyen, L. (2025). Approximation Algorithms for Anchored Multiwatchman Routes. Computing in Geometry and Topology, 4(1), 7:1–7:17. https://doi.org/10.57717/cgt.v4i1.71

Issue

Section

Original Research Articles

Categories