Metraipolis › archive › dc_0613ceed60e5

Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons — arXiv:2609.15510

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.15510
License (as archived)
CC0-1.0
Archived
2026-10-16T02:15:42.151Z
SHA-256 of the archived text
f11050fe2ed0d3dd9766db8dd517493dee75d70fdd38477008eaa5fa2e31ea92
Stable URL of this page
https://metraipolis.com/documento/dc_0613ceed60e5

How to cite

Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons — arXiv:2609.15510 — arXiv (en), https://arxiv.org/abs/2609.15510 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0613ceed60e5 (Metraipolis archive dc_0613ceed60e5, sha256 f11050fe2ed0d3dd9766db8dd517493dee75d70fdd38477008eaa5fa2e31ea92)
BibTeX
@misc{dc0613ceed60e5,
  title = {Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons — arXiv:2609.15510},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.15510},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0613ceed60e5; sha256 f11050fe2ed0d3dd9766db8dd517493dee75d70fdd38477008eaa5fa2e31ea92},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15510. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Art Gallery Problem (AGP) asks for the fewest guards that see all of a simple polygon. It is $\exists\mathbb{R}$-complete, hence NP-hard. We show that for a particular class of polygons, confining guards to a single edge makes AGP exactly and efficiently solvable. We call this the Strait Guarding Problem (SGP). Its input is a weak visibility polygon (WVP): a simple polygon where every point is seen from some point of one fixed edge, the base. SGP places the fewest guards on the base that jointly see the whole polygon. First, a structural fact: guards on the base edge that cover the boundary already cover the entire interior, turning a two-dimensional covering problem into a one-dimensional one. Our main result is the Witness-Guard Algorithm, which solves SGP exactly in $O((n + \mathrm{OPT} \cdot \rho)(\log n + \log \mathrm{OPT}))$ time, where $\rho$ is the number of reflex vertices in the WVP and OPT is the minimum number of guards. It is output-sensitive and certifies optimality by a witness set of size OPT derived from its output. We also study the guarding-the-vertex version and prove a tight $\Theta(n \log n)$ bound, with the lower bound following from Sorting. As a corollary of SGP, we obtain two results for altitude terrain guarding (ATG), a special case that SGP generalizes. We give a linear-time perfect-guarding algorithm, improving the previous $O(n^2 \log n)$ bound of Daescu, Friedrichs, Malik, Polishchuk and Schmidt. We also resolve their problem on the minimum guarding altitude, in $O(nk + k^2 \log k)$ time, improving on the $O(k^2 \lambda_{k-1}(n) \log n)$ bound of Kang, Kim and Ahn.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS).
Categorie arXiv: Computational Geometry (cs.CG) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.15510 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:54:07.142Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).