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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A Polynomial-Time Algorithm for Maximum Witness Set

Satyabrata Jana, Debabrata Pal, Sasanka Roy
arXiv (Cornell University)
Computational Geometry and Mesh Generation
preprint

A Polynomial-Time Algorithm for Maximum Witness Set

Satyabrata Jana, Debabrata Pal, Sasanka Roy
preprint en

Abstract

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.

arXiv (Cornell University)
Computational Geometry and Mesh Generation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon