A Polynomial-Time Algorithm for Maximum Witness Set
A witness set in a polygon is a set of points whose visibility regions are pairwise disjoint. Since no point of the polygon can see more than one witness, the cardinality of a witness set provides a lower bound on the minimum number of guards required to cover the polygon. Finding a maximum witness set is therefore a natural packing counterpart to the classical Art Gallery problem. While the latter is $\exists\mathbb{R}$-complete, the computational complexity of finding a maximum witness set in a general simple polygon has remained open. In this paper, we present a polynomial-time algorithm for computing a maximum witness set in a simple polygon with $n$ vertices, of which $ρ$ are reflex, assuming that no three vertices are collinear. Our algorithm runs in $\mathcal{O}(ρ^4n^6\log n)$ time. Our approach exploits a tree structure induced by witness visibility regions and employs geometric dynamic programming over nested regions determined by visibility windows.
Authors
- Satyabrata Jana (ORCID: https://orcid.org/0000-0002-7046-0091)
- Debabrata Pal (ORCID: https://orcid.org/0000-0001-6868-6078)
- Sasanka Roy
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.21498
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- preprint