DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.24

On the See-Through Watchman Route Problem and the Quota-TSP Problem on Infinite Lines

Authors: Joseph S. B. Mitchell and Linh Nguyen

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

The classic Watchman Route Problem (WRP) seeks to compute a shortest tour in a polygonal domain that sees every point of the domain. We introduce and study a novel generalization of the WRP, the See-Through Watchman Route Problem (STWRP), in which, in addition to vision-blocking "walls" of an input domain, there are obstacles to motion that are not opaque to vision: the watchman can see through certain obstacles or portions of the boundary of a polygonal domain P. This setting is motivated by real-world situations that may include transparent barriers (e.g., glass walls), obstacles that obstruct movement but not vision (e.g., lakes, flowerbeds, or potholes), and robotic sensors with penetration capabilities (e.g., microwave imaging). To the best of our knowledge, this version of the problem is new to the algorithms community. Our main result is an FPTAS for the STWRP in the case that P is an opaque-walled simple polygon having within it a set of transparent obstacles. A closely related problem that arises in this setting is that of the Traveling Salesperson problem with neighborhoods (TSPN) on a set of lines in the plane, with obstacles. We give the first FPTAS for the Quota-TSPN on infinite lines with polygonal obstacles. Additionally, we show tightness of our FPTAS, in that the Quota-TSPN on infinite lines with obstacles is weakly NP-hard. In the case of the STWRP within a simple polygon P with portions of the boundary, ∂ P, being transparent, we prove that the problem is NP-hard to approximate within a factor better than O(log n).

Cite as

Joseph S. B. Mitchell and Linh Nguyen. On the See-Through Watchman Route Problem and the Quota-TSP Problem on Infinite Lines. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mitchell_et_al:LIPIcs.ESA.2026.24,
  author =	{Mitchell, Joseph S. B. and Nguyen, Linh},
  title =	{{On the See-Through Watchman Route Problem and the Quota-TSP Problem on Infinite Lines}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.24},
  URN =		{urn:nbn:de:0030-drops-271605},
  doi =		{10.4230/LIPIcs.ESA.2026.24},
  annote =	{Keywords: Watchman route problem, TSP with neighborhoods}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2024.27

Optimizing Visibility-Based Search in Polygonal Domains

Authors: Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

Given a geometric domain P, visibility-based search problems seek routes for one or more mobile agents ("watchmen") to move within P in order to be able to see a portion (or all) of P, while optimizing objectives, such as the length(s) of the route(s), the size (e.g., area or volume) of the portion seen, the probability of detecting a target distributed within P according to a prior distribution, etc. The classic watchman route problem seeks a shortest route for an observer, with omnidirectional vision, to see all of P. In this paper we study bicriteria optimization problems for a single mobile agent within a polygonal domain P in the plane, with the criteria of route length and area seen. Specifically, we address the problem of computing a minimum length route that sees at least a specified area of P (minimum length, for a given area quota). We also study the problem of computing a length-constrained route that sees as much area as possible. We provide hardness results and approximation algorithms. In particular, for a simple polygon P we provide the first fully polynomial-time approximation scheme for the problem of computing a shortest route seeing an area quota, as well as a (slightly more efficient) polynomial dual approximation. We also consider polygonal domains P (with holes) and the special case of a planar domain consisting of a union of lines. Our results yield the first approximation algorithms for computing a time-optimal search route in P to guarantee some specified probability of detection of a static target within P, randomly distributed in P according to a given prior distribution.

Cite as

Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk. Optimizing Visibility-Based Search in Polygonal Domains. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{huynh_et_al:LIPIcs.SWAT.2024.27,
  author =	{Huynh, Kien C. and Mitchell, Joseph S. B. and Nguyen, Linh and Polishchuk, Valentin},
  title =	{{Optimizing Visibility-Based Search in Polygonal Domains}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.27},
  URN =		{urn:nbn:de:0030-drops-200671},
  doi =		{10.4230/LIPIcs.SWAT.2024.27},
  annote =	{Keywords: Quota watchman route problem, budgeted watchman route problem, visibility-based search, approximation}
}

Search Results

Documents authored by Nguyen, Linh

On the See-Through Watchman Route Problem and the Quota-TSP Problem on Infinite Lines

Abstract

Cite as

Optimizing Visibility-Based Search in Polygonal Domains

Abstract

Cite as

Thanks for your feedback!

Could not send message