arxiv: 2605.01592 · v1 · submitted 2026-05-02 · 💻 cs.CG

Recognition: 3 theorem links

· Lean Theorem

Witness Set: A Visibility Problem in NPcap XP

Bodhayan Roy, Debabrata Pal, Sasanka Roy, Satyabrata Jana

Authors on Pith no claims yet

Pith reviewed 2026-05-08 19:32 UTC · model grok-4.3

classification 💻 cs.CG

keywords Witness SetArt Gallery ProblemVisibilitySimple PolygonsNPXPDiscretizationParameterized Complexity

0 comments

The pith

Witness Set for simple polygons lies in NP and XP via a combinatorial discretization of size n to the power f of k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the Witness Set problem on simple polygons is solvable in nondeterministic polynomial time and in XP parameterized by k. It does so by constructing a finite set of candidate positions for witnesses whose size is bounded by n raised to some function of k. This discretization is purely combinatorial and does not rely on real algebraic geometry tools that are needed for the dual Art Gallery problem. A witness set is a collection of points such that no two points in the polygon share visibility to more than one of them. The result separates Witness Set from Art Gallery in complexity and yields an explicit n to the f of k time algorithm.

Core claim

For simple polygons the Witness Set problem admits a finite discretization of candidate witness positions of size n to the power f of k for some function f, which immediately places the problem in both NP and XP and produces a combinatorial algorithm running in that time bound.

What carries the argument

The finite discretization of candidate witness positions of size n^{f(k)} that suffices to test existence of any witness set of size k.

If this is right

Witness Set on simple polygons can be decided by an algorithm running in n^{f(k)} time.
The problem is in XP when parameterized by the size of the witness set.
The discrete variant restricted to a given finite point set is polynomial-time solvable on simple polygons.
The same discretization technique does not apply to rectilinear polygons with holes, where the discrete version is NP-complete.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The separation in complexity from Art Gallery suggests that visibility coverage problems may sometimes admit combinatorial rather than algebraic solutions depending on the direction of the optimization.
If the open question of NP-hardness for Witness Set on simple polygons is answered negatively, the discretization would immediately yield a polynomial-time algorithm for fixed k.
The same style of candidate-position bounding may extend to other dual visibility problems that ask for sets with limited rather than complete coverage.

Load-bearing premise

There exists a set of at most n to the power f of k candidate locations inside the polygon such that every possible witness set of size k can be replaced by one using only positions from this set.

What would settle it

A simple polygon together with an integer k whose smallest witness set uses at least one position lying strictly outside every candidate set of size n^{f(k)} constructed by the discretization method.

read the original abstract

We study the Witness Set problem, a natural dual to the classical Art Gallery problem. In the Witness Set problem, we are given a polygon $P$ and an integer $k$ as input, and the objective is to determine whether $P$ has a witness set of size at least $k$. A point set $X$ in $P$ is called a witness set if every point in $P$ is visible from at most one point in $X$. For simple polygons, we show that Witness Set lies in both $NP$ and $XP$. This stands in sharp contrast to its dual, the Art Gallery problem, which was recently shown to be $\exists \mathbb{R}$-complete by Abrahamsen et al. and is therefore neither in $NP$ nor admits a polynomial-size discretization unless $NP=\exists \mathbb{R}$. In contrast, we prove that Witness Set for simple polygons admits a finite discretization of size $n^{f(k)}$ for some function $f$. For comparison, even for simple polygons, Efrat and Har-Peled gave an algorithm for Art Gallery running in time $n^{O(k)}$ using tools from real algebraic geometry, and it appears difficult to obtain such algorithms without this machinery. On the other hand, our approach for Witness Set is purely combinatorial and relies on discretization, leading to an $n^{f(k)}$-time algorithm. Although Amit et al. claimed more than fifteen years ago that Witness Set is $NP$-hard, no proof or reference was provided. We show that the discrete version of the Witness Set problem - where the witness set must be chosen from a given finite point set $Q$ (instead of allowing witnesses to be chosen anywhere in the polygon), referred to as Discrete Witness Set - is $NP$-complete, even when the input is restricted to rectilinear polygons with holes. However, for simple polygons, Discrete Witness Set admits a polynomial-time algorithm by Das et al. Thus, it remains an open question whether the Witness Set problem is $NP$-hard.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows Witness Set on simple polygons is in NP ∩ XP via a combinatorial discretization of size n^{f(k)}, giving a clean contrast to Art Gallery hardness without algebraic geometry.

read the letter

The main thing to know is that this paper puts the Witness Set problem for simple polygons into NP and XP using a combinatorial discretization. If a set of k witnesses exists, then one using only a specific set of n^{f(k)} candidate points also exists. This gives both the XP algorithm by brute force on subsets and the NP certificate via combinatorial descriptors. The new part is the discretization itself, built from intersections of lines defined by pairs of vertices and accounting for k-wise visibility types. It is purely combinatorial, which is a plus compared to the algebraic geometry needed for the dual Art Gallery problem. The authors also settle the discrete version as NP-complete for rectilinear polygons with holes, while noting it is polynomial-time solvable for simple polygons. This addresses an old unproven claim from Amit et al. without overclaiming. The argument holds up. The verification for NP uses standard O(n) visibility polygon computations and checks for disjoint coverage. No internal contradictions or unsupported steps appear in the construction. One minor soft spot is that the function f(k) remains unspecified in detail, leaving the precise runtime unclear beyond the XP classification. Another is that the continuous problem's NP-hardness is still open, though the paper does not pretend to close it. These are not load-bearing issues. This paper is for researchers in computational geometry focused on visibility problems and parameterized complexity. Readers working on art gallery variants or discretization techniques will get the most from it, especially the contrast in complexity behaviors. It deserves a serious referee. The results are grounded and the approach is honest. I recommend sending it for peer review.

Referee Report

0 major / 3 minor

Summary. The paper studies the Witness Set problem: given a polygon P and integer k, decide whether there exists a set X of k points in P such that every point in P is visible from at most one point in X. For simple polygons, the authors claim membership in both NP and XP by constructing a finite discretization of candidate witness positions whose size is bounded by n^{f(k)} for some function f; this discretization supports an XP algorithm via enumeration of k-subsets and a polynomial-time verifiable NP certificate based on combinatorial descriptors of the witnesses. They further prove NP-completeness of the discrete variant (witnesses restricted to a given point set) on rectilinear polygons with holes, note a known polynomial-time algorithm for the discrete case on simple polygons, and leave open whether the continuous Witness Set problem is NP-hard.

Significance. If the discretization holds, the result is significant for placing a natural visibility problem in NP ∩ XP via purely combinatorial arguments, in direct contrast to the ∃R-completeness of the dual Art Gallery problem even for simple polygons. The approach yields an n^{f(k)}-time algorithm without real-algebraic-geometry machinery (unlike prior Art Gallery algorithms) and clarifies the complexity landscape between continuous and discrete variants of visibility problems.

minor comments (3)

[§3] §3 (Discretization construction): the proof that every witness set of size k has an equivalent one using only the enumerated critical points (intersections of vertex-pair lines under k-wise combinatorial types) should explicitly state the degree of the polynomial in the n^{f(k)} bound and confirm that the combinatorial types are enumerable in n^{O(f(k))} time.
[Abstract, §1] Abstract and §1: the function f(k) is left unspecified; provide at least its asymptotic form or a concrete upper bound (e.g., O(k^2)) in the main body to make the XP claim fully quantitative.
[§4] §4 (NP certificate): the verifier's running time for computing visibility polygons and checking pairwise disjointness is stated as polynomial, but the precise degree (using the O(n) visibility algorithm) should be recorded to confirm it is independent of k.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our manuscript and for recommending minor revision. The assessment of significance is appreciated, particularly the contrast drawn with the Art Gallery problem. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation for Witness Set membership in NP ∩ XP on simple polygons rests on a direct combinatorial construction of a candidate discretization whose size is bounded by n^{f(k)}; the proof enumerates critical visibility intersection points and combinatorial types to show that any witness set of size k has an equivalent one drawn from this finite set. This discretization is then used for the XP enumeration algorithm and for the NP certificate (k descriptors of size O(k log n) with polynomial-time visibility verification). No equation reduces to a prior fit, no uniqueness theorem is imported from self-citation, and the argument does not rename or smuggle an ansatz; it is self-contained against external combinatorial visibility primitives.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard geometric definitions and a paper-specific discretization whose details are not provided in the abstract.

axioms (2)

domain assumption Polygons are simple closed regions in the plane with visibility defined by straight-line segments lying entirely within the polygon.
Standard assumption in computational geometry invoked in the problem definition.
ad hoc to paper A finite discretization of size n^{f(k)} captures all possible witness sets of size k.
Central to the XP membership claim but not detailed in the abstract.

pith-pipeline@v0.9.0 · 5693 in / 1453 out tokens · 74728 ms · 2026-05-08T19:32:05.300397+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

58 extracted references · 27 canonical work pages

[1]

1991 , publisher=

Computing two-covers of simple polygons , author=. 1991 , publisher=

1991
[2]

2016 , doi =

24th Annual European Symposium on Algorithms,. 2016 , doi =

2016
[3]

Intersection graphs of segments and $\exists\mathbb{R}$

Jir. Intersection graphs of segments and. CoRR , volume =. 2014 , url =. 1406.2636 , timestamp =

work page Pith review arXiv 2014
[4]

Canny , editor =

John F. Canny , editor =. Some Algebraic and Geometric Computations in. Proceedings of the 20th Annual. 1988 , doi =

1988
[5]

CoRR , volume =

Lucas Meijer and Tillmann Miltzow , title =. CoRR , volume =. 2022 , doi =. 2212.01211 , timestamp =

work page arXiv 2022
[6]

Supowit , title =

Joseph O'Rourke and Kenneth J. Supowit , title =. 1983 , doi =

1983
[7]

Eidenbenz and Christoph Stamm and Peter Widmayer , title =

Stephan J. Eidenbenz and Christoph Stamm and Peter Widmayer , title =. Algorithmica , volume =. 2001 , doi =

2001
[8]

Journal of Mathematical Analysis and Applications , volume=

Triangulated graphs and the elimination process , author=. Journal of Mathematical Analysis and Applications , volume=. 1970 , publisher=

1970
[9]

Demaine and Sanjay E

Ajay Deshpande and Taejung Kim and Erik D. Demaine and Sanjay E. Sarma , editor =. Algorithms and Data Structures, 10th International Workshop,. 2007 , doi =

2007
[10]

Mark de Berg and Amirali Khosravi , title =. Int. J. Comput. Geom. Appl. , volume =. 2012 , url =. doi:10.1142/S0218195912500045 , timestamp =

work page doi:10.1142/s0218195912500045 2012
[12]

Background , booktitle=

Ghosh, Subir Kumar , year=. Background , booktitle=
[13]

CoRR , volume =

Udvas Das and Binayak Dutta and Satyabrata Jana and Debabrata Pal and Sasanka Roy , title =. CoRR , volume =. 2025 , doi =

2025
[14]

Lorentz Workshop on Fixed-Parameter Computational Geometry, Leiden, the Netherlands , volume=

Open problems: Guarding problems , author=. Lorentz Workshop on Fixed-Parameter Computational Geometry, Leiden, the Netherlands , volume=
[15]

Mikkel Abrahamsen , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00045 , timestamp =

work page doi:10.1109/focs52979.2021.00045 2021
[16]

Akanksha Agrawal and Kristine V. K. Knudsen and Daniel Lokshtanov and Saket Saurabh and Meirav Zehavi , title =. Discret. Comput. Geom. , volume =. 2024 , url =. doi:10.1007/S00454-023-00569-Y , timestamp =

work page doi:10.1007/s00454-023-00569-y 2024
[17]

Holmsen and Tillmann Miltzow , title =

Michael Gene Dobbins and Andreas F. Holmsen and Tillmann Miltzow , title =. CoRR , volume =. 2018 , eprinttype =. 1811.01177 , timestamp =

work page arXiv 2018
[18]

Katz and Joseph S

Rathish Das and Omrit Filtser and Matthew J. Katz and Joseph S. B. Mitchell , editor =. 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece , series =. 2024 , doi =

2024
[19]

McConnell and Jeremy P

Ross M. McConnell and Jeremy P. Spinrad , title =. Discret. Math. , volume =. 1999 , url =. doi:10.1016/S0012-365X(98)00319-7 , timestamp =

work page doi:10.1016/s0012-365x(98)00319-7 1999
[20]

Reilly Browne and Prahlad Narasimhan Kasthurirangan and Joseph S. B. Mitchell and Valentin Polishchuk , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00083 , timestamp =

work page doi:10.1109/focs57990.2023.00083 2023
[22]

Nilsson , title =

Erik Krohn and Bengt J. Nilsson , title =. Algorithmica , volume =. 2013 , doi =

2013
[23]

Alon Efrat and Sariel Har. Inf. Process. Lett. , volume =. 2006 , doi =

2006
[24]

Hengeveld and Tillmann Miltzow , editor =

Simon B. Hengeveld and Tillmann Miltzow , editor =. A Practical Algorithm with Performance Guarantees for the Art Gallery Problem , booktitle =. 2021 , doi =

2021
[25]

Fomin and Sudeshna Kolay and Saket Saurabh and Meirav Zehavi , title =

Pradeesha Ashok and Fedor V. Fomin and Sudeshna Kolay and Saket Saurabh and Meirav Zehavi , title =. 2018 , url =. doi:10.1145/3186897 , timestamp =

work page doi:10.1145/3186897 2018
[26]

Parameter Analysis for Guarding Terrains , booktitle =

Akanksha Agrawal and Sudeshna Kolay and Meirav Zehavi , editor =. Parameter Analysis for Guarding Terrains , booktitle =. 2020 , url =. doi:10.4230/LIPIcs.SWAT.2020.4 , timestamp =

work page doi:10.4230/lipics.swat.2020.4 2020
[27]

2011 , url =

James King and Erik Krohn , title =. 2011 , url =. doi:10.1137/100791506 , timestamp =

work page doi:10.1137/100791506 2011
[28]

B. J. Nilsson , title =
[29]

Guarding lines and 2-link polygons is apx-hard , booktitle =

Bj. Guarding lines and 2-link polygons is apx-hard , booktitle =. 2001 , crossref =

2001
[30]

D. T. Lee and Arthur K. Lin , title =. 1986 , doi =

1986
[31]

Alok Aggarwal , title =
[32]

Two NP-Hard Art-Gallery Problems for Ortho-Polygons , journal =

Dietmar Schuchardt and Hans. Two NP-Hard Art-Gallery Problems for Ortho-Polygons , journal =. 1995 , url =. doi:10.1002/malq.19950410212 , timestamp =

work page doi:10.1002/malq.19950410212 1995
[33]

Algorithmica , volume=

Approximate guarding of monotone and rectilinear polygons , author=. Algorithmica , volume=. 2013 , publisher=

2013
[34]

, author=

Optimal guarding of polygons and monotone chains. , author=. CCCG , pages=
[35]

24th Canadian Conference on Computational Geometry, August 8-10, 2012 Charlottetown, Canada; , year=

The complexity of guarding monotone polygons , author=. 24th Canadian Conference on Computational Geometry, August 8-10, 2012 Charlottetown, Canada; , year=

2012
[36]

Mark Keil and Anil Maheshwari and Saeed Mehrabi and Debajyoti Mondal and Michiel H

Prosenjit Bose and Paz Carmi and J. Mark Keil and Anil Maheshwari and Saeed Mehrabi and Debajyoti Mondal and Michiel H. M. Smid , editor =. Computing Maximum Independent Set on Outerstring Graphs and Their Relatives , booktitle =. 2019 , url =. doi:10.1007/978-3-030-24766-9\_16 , timestamp =

work page doi:10.1007/978-3-030-24766-9 2019
[37]

Martin Charles Golumbic and Doron Rotem and Jorge Urrutia , title =. Discret. Math. , volume =. 1983 , url =. doi:10.1016/0012-365X(83)90019-5 , timestamp =

work page doi:10.1016/0012-365x(83)90019-5 1983
[38]

Ovidiu Daescu and Stephan Friedrichs and Hemant Malik and Valentin Polishchuk and Christiane Schmidt , title =. Comput. Geom. , volume =. 2019 , doi =

2019
[39]

doi:10.1109/access.2020.2994052 , url =

Shantanu Das and Paola Flocchini and Giuseppe Prencipe and Nicola Santoro , title =. doi:10.1109/access.2020.2994052 , url =

work page doi:10.1109/access.2020.2994052 2020
[40]

Peter Babington , title =
[41]

Subir Kumar Ghosh , title =. Discret. Appl. Math. , volume =. 2010 , url =. doi:10.1016/j.dam.2009.12.004 , timestamp =

work page doi:10.1016/j.dam.2009.12.004 2010
[42]

2017 , doi =

33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia , series =. 2017 , doi =

2017
[43]

2019 , url =

Orthogonal Terrain Guarding is NP-complete , journal =. 2019 , url =. doi:10.20382/jocg.v10i2a3 , timestamp =

work page doi:10.20382/jocg.v10i2a3 2019
[44]

2017 , url =

An Approximation Algorithm for the Art Gallery Problem , booktitle =. 2017 , url =. doi:10.4230/LIPIcs.SoCG.2017.20 , timestamp =

work page doi:10.4230/lipics.socg.2017.20 2017
[45]

Stephan Friedrichs and Michael Hemmer and James King and Christiane Schmidt , title =. J. Comput. Geom. , volume =. 2016 , url =. doi:10.20382/jocg.v7i1a13 , timestamp =

work page doi:10.20382/jocg.v7i1a13 2016
[46]

Yoav Amit and Joseph S. B. Mitchell and Eli Packer , title =. Int. J. Comput. Geom. Appl. , volume =. 2010 , url =. doi:10.1142/S0218195910003451 , timestamp =

work page doi:10.1142/s0218195910003451 2010
[47]

Katz and Gabriel S

Matthew J. Katz and Gabriel S. Roisman , title =. Comput. Geom. , volume =. 2008 , url =. doi:10.1016/j.comgeo.2007.02.002 , timestamp =

work page doi:10.1016/j.comgeo.2007.02.002 2008
[48]

Mikkel Abrahamsen and Anna Adamaszek and Tillmann Miltzow , title =. J. 2022 , url =. doi:10.1145/3486220 , timestamp =

work page doi:10.1145/3486220 2022
[49]

2006 , publisher=

Algorithms in real algebraic geometry , author=. 2006 , publisher=

2006
[50]

2018 , volume =

Intersection Graphs of Rays and Grounded Segments , journal =. 2018 , volume =

2018
[51]

Mark Keil , title =

Chris Worman and J. Mark Keil , title =. Int. J. Comput. Geom. Appl. , volume =. 2007 , url =. doi:10.1142/S0218195907002264 , timestamp =

work page doi:10.1142/s0218195907002264 2007
[52]

D. T. Lee , title =. Comput. Vis. Graph. Image Process. , volume =. 1983 , doi =

1983
[53]

17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976 , pages =

Michael Ian Shamos and Dan Hoey , title =. 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976 , pages =. 1976 , doi =

1976
[54]

Rajeev Motwani and Arvind Raghunathan and Huzur Saran , title =. J. Comput. Syst. Sci. , volume =. 1990 , url =. doi:10.1016/0022-0000(90)90017-F , timestamp =

work page doi:10.1016/0022-0000(90)90017-f 1990
[55]

Randolph Franklin , title =

Wm. Randolph Franklin , title =. 1989 , url =. doi:10.1137/1031076 , timestamp =

work page doi:10.1137/1031076 1989
[56]

Ian Munro , title =

Prosenjit Bose and Anna Lubiw and J. Ian Munro , title =. Comput. Geom. , volume =. 2002 , url =. doi:10.1016/S0925-7721(01)00070-0 , timestamp =

work page doi:10.1016/s0925-7721(01)00070-0 2002
[57]

Master’s thesis , pages=

Computing two-covers of simple polygons, Master’s thesis , author=. Master’s thesis , pages=. 1991 , publisher=

1991
[58]

, title =

O'Rourke, J. , title =. 1987 , publisher =

1987
[59]

2007 , isbn =

Ghosh, Subir , title =. 2007 , isbn =

2007
[60]

Mark Keil and Joseph S.B

J. Mark Keil and Joseph S.B. Mitchell and Dinabandhu Pradhan and Martin Vatshelle , keywords =. An algorithm for the maximum weight independent set problem on outerstring graphs , journal =. 2017 , note =. doi:https://doi.org/10.1016/j.comgeo.2016.05.001 , url =

work page doi:10.1016/j.comgeo.2016.05.001 2017