Metraipolis › archive › dc_205665c811aa

Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable — arXiv:2609.24460

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.24460
License (as archived)
CC0-1.0
Archived
2026-10-09T22:40:57.360Z
SHA-256 of the archived text
f4debe89f1179078d95064d25a40d819932204d832c93520716bafdd86dab6c4
Stable URL of this page
https://metraipolis.com/documento/dc_205665c811aa

How to cite

Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable — arXiv:2609.24460 — arXiv (en), https://arxiv.org/abs/2609.24460 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_205665c811aa (Metraipolis archive dc_205665c811aa, sha256 f4debe89f1179078d95064d25a40d819932204d832c93520716bafdd86dab6c4)
BibTeX
@misc{dc205665c811aa,
  title = {Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable — arXiv:2609.24460},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24460},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_205665c811aa; sha256 f4debe89f1179078d95064d25a40d819932204d832c93520716bafdd86dab6c4},
  year = {2026}
}

Archived text

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

In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point. The Witness Set Problem (WSP), introduced by Amit, Mitchell, and Packer, is a natural dual to the AGP. In this paper, we study the WSP in weak visibility polygons (WVPs), the simple polygons in which every point is seen from some point of one fixed edge. A witness set is a set of points whose visibility regions are pairwise disjoint, so that no single guard sees two of them. A maximum witness set, therefore, lower-bounds the guard number. Exact polynomial-time algorithms for the WSP are known only for monotone mountains, a proper subclass of WVPs. We give the first exact polynomial-time algorithms for the WSP in WVPs, in two settings. In the Discrete Witness Set Problem (DiscWSP), the witnesses come from a given set of $m$ points, and we find a maximum witness subset in $O(n + m \log(n+m))$ time on an $n$-vertex polygon. The algorithm rests on a structural fact: the visibility intersection graph of a WVP, in which two points are adjacent if their visibility regions intersect, is a trapezoid graph, that is, an intersection graph of trapezoids between two parallel lines. Moreover, the class of these graphs properly contains the interval graphs and the permutation graphs, which may be of independent interest in graph theory. We also prove an $\Omega(n \log n)$ lower bound in the algebraic decision-tree model for instances with $m = \Theta(n)$, so our algorithm for DiscWSP is optimum. In the Continuous Witness Set Problem (ContWSP), a witness may be any point of the polygon, and we give an exact algorithm running in $O(n \log n + \rho^{2}(n + \rho^{2}))$ time, where $\rho$ is the number of reflex vertices.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 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.24460 — 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-09T22:24:05.690Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).