pith. sign in

arxiv: 2512.23297 · v2 · submitted 2025-12-29 · 💻 cs.CG · cs.DM· cs.DS

A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem

Khaled Elbassioni This is my paper

Pith reviewed 2026-05-16 19:39 UTC · model grok-4.3

classification 💻 cs.CG cs.DMcs.DS
keywords art gallery problemapproximation algorithmsvisibilitypolygons with holesdeterministic algorithmsbicriteria approximationarea coverage
0
0 comments X

The pith

A deterministic algorithm finds a guard set of logarithmic size that covers nearly all the area of any polygon with holes.

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

This paper develops a deterministic method to approximate solutions to the art gallery problem for polygons that may contain holes. The algorithm returns a collection of points inside the polygon whose number is bounded by a product of logarithms times the optimal number, and these points collectively see at least a (1 minus delta) fraction of the polygon's total area. The procedure runs in time that is polynomial in the number of vertices, the number of holes, the bit length of the coordinates, and the logarithm of one over delta. Readers interested in computational geometry would value this because exact solutions are computationally hard, so this provides a reliable way to get close to optimal area visibility without relying on random choices.

Core claim

Given any polygon H with h holes, n rational vertices of maximum bit-length L, and a parameter δ ∈ (0,1), there exists a deterministic algorithm that computes a set of points in H of size O(OPT · log(h+2) · log(OPT · log(h+2))) that sees at least a (1−δ)-fraction of the area of H, with running time polynomial in h, n, L and log(1/δ), where OPT is the size of an optimum solution.

What carries the argument

The deterministic bicriteria approximation algorithm that uses discretization of the visibility space to select a small set of guards while guaranteeing near-complete area coverage.

If this is right

  • The result applies directly to polygons with holes, extending previous work on simple polygons.
  • Area coverage can be achieved to arbitrary precision (1-δ) in polynomial time depending on log(1/δ).
  • Only rational vertex coordinates with bounded bit length are required for the guarantees to hold.
  • The size bound is O(OPT log(h+2) log(OPT log(h+2))), providing a concrete approximation factor.

Where Pith is reading between the lines

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

  • This bicriteria approach could inspire similar methods for other coverage problems in geometry where exact optimization is intractable.
  • Practical implementations might focus on implementing the discretization step to handle real-world floor plans efficiently.
  • Connections to set cover approximations suggest potential improvements using more advanced sampling techniques.

Load-bearing premise

The proof depends on the existence of a discretization or sampling of possible guard positions that preserves the area coverage while keeping the number of guards within the logarithmic bound.

What would settle it

A concrete counterexample would be a polygon with holes where no set of that size covers (1-δ) of the area, or an instance where the algorithm fails to run in the claimed polynomial time.

Figures

Figures reproduced from arXiv: 2512.23297 by Khaled Elbassioni.

Figure 1
Figure 1. Figure 1: Visibility regions in a polygon. of the largest subset of Q shattered by F. If arbitrarily large subsets of Q can be shattered then VC-dim(F) = +∞. Given a polygon H, we can define a range space FH = (Q, R), where Q = H and R = {V(q) : q ∈ H}. Valtr [42] showed that VC-dim(FH) ≤ 23 for any simple polygon H (i.e., a polygon without holes) and that VC-dim(FH) = O(log h) for any polygon H with h holes. For si… view at source ↗
Figure 2
Figure 2. Figure 2: The partition of H defined by the set of points Pt for t = 2. Data: A polygon H and approximation accuracies ε, δ, ν ∈ (0, 1) Result: A ( 1+2ε 1−ν , 1 − δ)-approximate solution P ⊆ H 1 t ← 0; P0 ← ∅; T ← 1 ε 2 ln 1 δ ; H0 ← H 2 w0(q) ← 1 for all q ∈ H0 3 while area(Ht) ≥ δ · area(H) do 4 pt+1 ← Max(H, Ht , wt , ν) 5 Pt+1 ← Pt ∪ {pt+1} 6 for q ∈ H do // Implicitly 7 wt+1(q) ←  (1 − ε)wt(q) if q ∈ V(pt+1) ∩… view at source ↗
Figure 3
Figure 3. Figure 3: The refined partition C ′ 1 (H) obtained from C1(H) by adding all line segments between any pair of internal vertices of C1(H) and between any internal vertex of C1(H) and a vertex of H. For clarity of presentation, only some of the added segments are shown (as dashed lines). (a) A cell R ∈ Ct(H) and a cell Q in the refinement C ′ t (H). Any two points q, q′ ∈ Q see exactly the same set of points from the … view at source ↗
Figure 4
Figure 4. Figure 4: The visibility polygon of a point q ∈ Q inside R ∈ Ct(H), where Q ∈ C′ t (H). 10 [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Rounding the polygonal arrangement Ct(H). Proof. Two sets contribute to the difference Ht \ Het : the set of small cells, and the truncated parts of the larges cells S R∈Lt: Pt(R)<T R\Re. Note that the total area of the small cells is at most rt · 4ρD. On the other hand, for any R ∈ Lt , we have area(R) − area(Re) ≤ 2ρ · prem(R), where prem(P) is the length of the perimeter of R. This inequality holds beca… view at source ↗
read the original abstract

Given a polygon $H$ in the plane, the art gallery problem calls for fining the smallest set of points in $H$ from which every other point in $H$ is seen. We give a deterministic algorithm that, given any polygon $H$ with $h$ holes, $n$ rational veritces of maximum bit-length $L$, and a parameter $\delta \in(0,1)$, is guaranteed to find a set of points in $H$ of size $O\big(\OPT\cdot\log(h+2)\cdot\log (\OPT\cdot\log(h+2)))$ that sees at least a $(1-\delta)$-fraction of the area of the polygon. The running time of the algorithm is polynomial in $h$, $n$, $L$ and $\log(\frac{1}{\delta})$, where $\OPT$ is the size of an optimum solution.

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.

Referee Report

1 major / 1 minor

Summary. The manuscript presents a deterministic bicriteria approximation algorithm for the art gallery problem. Given a polygon H with h holes, n rational vertices of bit-length L, and δ ∈ (0,1), the algorithm returns a set of O(OPT · log(h+2) · log(OPT · log(h+2))) guards that cover at least a (1−δ)-fraction of the area of H, with running time polynomial in n, h, L, and log(1/δ).

Significance. If the discretization and sampling arguments are correct, this constitutes a meaningful advance: the first deterministic polynomial-time bicriteria result for approximate area coverage in polygons with holes. The approximation factors are logarithmic in the natural parameters and the dependence on log(1/δ) is efficient, improving on prior randomized or weaker deterministic bounds for visibility coverage problems.

major comments (1)
  1. [Algorithm and proof of correctness (discretization step)] The discretization of the visibility space (likely described in the section constructing the candidate guard set G and sample S) must be shown to produce |S| polynomial in n, h, L, log(1/δ) while ensuring that any cover of S by G covers (1−δ) area and that the discrete OPT on (G,S) is O(OPT). The Θ(n²) complexity of the visibility arrangement for polygons with holes makes this non-trivial; the current sketch does not rule out an extra log(1/δ) blow-up in the discrete optimum that the subsequent O(log(h+2) log(OPT log(h+2))) set-cover approximation cannot absorb.
minor comments (1)
  1. [Abstract] Abstract contains two typos: 'fining' should be 'finding' and 'veritces' should be 'vertices'.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of our result and for highlighting the need for a more rigorous treatment of the discretization argument. We address the concern point-by-point below and will strengthen the relevant sections in the revision.

read point-by-point responses

  1. Referee: [Algorithm and proof of correctness (discretization step)] The discretization of the visibility space (likely described in the section constructing the candidate guard set G and sample S) must be shown to produce |S| polynomial in n, h, L, log(1/δ) while ensuring that any cover of S by G covers (1−δ) area and that the discrete OPT on (G,S) is O(OPT). The Θ(n²) complexity of the visibility arrangement for polygons with holes makes this non-trivial; the current sketch does not rule out an extra log(1/δ) blow-up in the discrete optimum that the subsequent O(log(h+2) log(OPT log(h+2))) set-cover approximation cannot absorb.

    Authors: We agree that the discretization step requires a fully expanded proof rather than a sketch. In the revised manuscript we will add a new Lemma (in Section 4) that explicitly constructs G as the vertices plus an O(n²)-size discretization of all edges (with bit-length controlled by L) and constructs S by taking one representative point from each face of the visibility arrangement together with a deterministic low-discrepancy subdivision of each face into O(log(1/δ)) subcells whose areas are at most δ·area(H)/poly(n,h). This yields |S| = O(n² h² log(1/δ)), which is polynomial in the allowed parameters. We prove two directions: (i) any cover of S leaves at most a δ-fraction of the area uncovered, because each subcell is either fully covered or contributes at most its area bound; (ii) there exists a cover of S of size at most 4·OPT (by perturbing an optimal continuous solution to the nearest sample points inside the same visibility cell). Consequently the discrete optimum is O(OPT) with no multiplicative log(1/δ) factor. The subsequent O(log(h+2) log(OPT log(h+2))) set-cover approximation is therefore applied to an instance whose optimum is already O(OPT), preserving the claimed overall bound. We will include all constants and the arrangement-complexity argument in the revision. revision: yes

Circularity Check

0 steps flagged

No circularity: approximation bound expressed in terms of independent OPT with no self-referential reduction

full rationale

The claimed result is a standard bicriteria approximation: an algorithm producing O(OPT log(h+2) log(OPT log(h+2))) guards covering (1-δ) area, with running time polynomial in the input parameters. OPT is defined externally as the optimum guard count; the output size is an explicit multiplicative factor applied to this independent quantity rather than a fitted or renamed parameter. No equations, self-citations, or ansatzes in the provided abstract reduce the guarantee to a tautology or to prior self-work. The discretization step mentioned in the skeptic note is a correctness concern (transfer of area guarantee) but does not create a definitional loop where the claimed size bound is forced by construction from the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only: no explicit free parameters beyond the input δ and the definition of OPT; no new entities postulated; relies on standard assumptions of computational geometry such as rational vertex coordinates and polygonal visibility.

pith-pipeline@v0.9.0 · 5447 in / 1175 out tokens · 39907 ms · 2026-05-16T19:39:55.603581+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 2 internal anchors

  1. [1]

    Abrahamsen, A

    M. Abrahamsen, A. Adamaszek, and T. Miltzow. Irrational guards are sometimes needed. In Boris Aronov and Matthew J. Katz, editors,33rd International Symposium on Compu- tational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, volume 77 ofLIPIcs, pages 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2017

    work page 2017

  2. [2]

    Abrahamsen, A

    M. Abrahamsen, A. Adamaszek, and T. Miltzow. The art gallery problem is∃∖-complete. J. ACM, 69(1):4:1–4:70, 2022

    work page 2022

  3. [3]

    P. K. Agarwal, E. Ezra, and M. Sharir. Near-linear approximation algorithms for geometric hitting sets.Algorithmica, 63(1):1–25, 2012

    work page 2012

  4. [4]

    P. K. Agarwal and J. Pan. Near-linear algorithms for geometric hitting sets and set covers. Discret. Comput. Geom., 63(2):460–482, 2020

    work page 2020

  5. [5]

    Alon and J

    N. Alon and J. H. Spencer.The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2008

    work page 2008

  6. [6]

    Arora, E

    S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta- algorithm and applications.Theory of Computing, 8(1):121–164, 2012

    work page 2012

  7. [7]

    S. Basu, R. Pollack, and M. Roy. On the combinatorial and algebraic complexity of quan- tifier elimination.J. ACM, 43(6):1002–1045, 1996

    work page 1996

  8. [8]

    An Approximation Algorithm for the Art Gallery Problem

    ´E. Bonnet and T. Miltzow. An approximation algorithm for the art gallery problem. In European Workshop on Computational Geometry, EuroCG’16, also available online as: https://arxiv.org/abs/1607.05527, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  9. [9]

    Bonnet and T

    ´E. Bonnet and T. Miltzow. An approximation algorithm for the art gallery problem. In Boris Aronov and Matthew J. Katz, editors,33rd International Symposium on Computa- tional Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, volume 77 ofLIPIcs, pages 20:1–20:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2017

    work page 2017

  10. [10]

    Br¨ onnimann, B

    H. Br¨ onnimann, B. Chazelle, and J. Matouˇ sek. Product range spaces, sensitive sampling, and derandomization.SIAM Journal on Computing, 28(5):1552–1575, 1999

    work page 1999

  11. [11]

    Br¨ onnimann and M

    H. Br¨ onnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(4):463–479, 1995

    work page 1995

  12. [12]

    Chazelle.The Discrepancy Method: Randomness and Complexity

    B. Chazelle.The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York, NY, USA, 2000

    work page 2000

  13. [13]

    Chazelle and J

    B. Chazelle and J. Matouˇ sek. On linear-time deterministic algorithms for optimization problems in fixed dimension.Journal of Algorithms, 21(3):579 – 597, 1996

    work page 1996

  14. [14]

    Cheong, A

    O. Cheong, A. Efrat, and S. Har-Peled. Finding a guard that sees most and a shop that sells most.Discrete & Computational Geometry, 37(4):545–563, 2007

    work page 2007

  15. [15]

    Csik´ os and N

    M. Csik´ os and N. H. Mustafa. Optimal approximations made easy.Information Processing Letters, 176:106250, 2022

    work page 2022

  16. [16]

    de Berg, O

    M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars.Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. 14

    work page 2008

  17. [17]

    Deshpande, T

    A. Deshpande, T. Kim, E. D. Demaine, and S. E. Sarma. A pseudopolynomial time O(logn)-approximation algorithm for art gallery problems. InProceedings of the tenth International Workshop on Algorithms and Data Structures, WADS ’07, pages 163–174. Springer, 2007

    work page 2007

  18. [18]

    Dinur and D

    I. Dinur and D. Steurer. Analytical approach to parallel repetition. InProceedings of the forty-sixth annual ACM symposium on Theory of Computing, STOC’ 14, pages 624–633, 2014

    work page 2014

  19. [19]

    Efrat and S

    A. Efrat and S. Har-Peled. Guarding galleries and terrains.Inf. Process. Lett., 100(6):238– 245, 2006

    work page 2006

  20. [20]

    Eidenbenz, C

    S. Eidenbenz, C. Stamm, and P. Widmayer. Inapproximability results for guarding poly- gons and terrains.Algorithmica, 31(1):79–113, 2001

    work page 2001

  21. [21]

    Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension

    K. Elbassioni. Finding small hitting sets in infinite range spaces of bounded VC-dimension. CoRR, abs/1610.03812, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  22. [22]

    Elbassioni

    K. Elbassioni. Finding small hitting sets in infinite range spaces of bounded VC-dimension. In33rd International Symposium on Computational Geometry, SoCG 2017, pages 40:1– 40:15, 2017

    work page 2017

  23. [23]

    Elbassioni

    K. Elbassioni. A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces.Oper. Res. Lett., 51(5):507–514, 2023

    work page 2023

  24. [24]

    G. Even, D. Rawitz, and S. (M.) Shahar. Hitting sets when the VC-dimension is small. Inf. Process. Lett., 95(2):358–362, July 2005

    work page 2005

  25. [25]

    Garg and J

    N. Garg and J. K¨ onemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems.SIAM J. Comput., 37(2):630–652, 2007

    work page 2007

  26. [26]

    S. K. Ghosh. Approximation algorithms for art gallery problems in polygons.Canad. Information Processing Soc. Congress., pages 429–434, 1987

    work page 1987

  27. [27]

    S. K. Ghosh. Approximation algorithms for art gallery problems in polygons.Discrete Applied Mathematics, 158(6):718 – 722, 2010

    work page 2010

  28. [28]

    Gilbers and R

    A. Gilbers and R. Klein. A new upper bound for the VC-dimension of visibility regions. Computational Geometry, 47(1):61 – 74, 2014

    work page 2014

  29. [29]

    Grigoriev and N

    D. Grigoriev and N. Vorobjov. Solving systems of polynomial inequalities in subexponential time.J. Symb. Comput., 5(1/2):37–64, 1988

    work page 1988

  30. [30]

    Har-Peled and M

    S. Har-Peled and M. Sharir. Relative (p,ϵ)-approximations in geometry.Discrete & Computational Geometry, 45(3):462–496, 2011

    work page 2011

  31. [31]

    Haussler and E

    D. Haussler and E. Welzl. Epsilon-nets and simplex range queries.Discrete & Computa- tional Geometry, 2:127–151, 1987

    work page 1987

  32. [32]

    J. King. Fast vertex guarding for polygons with and without holes.Comput. Geom., 46(3):219–231, 2013

    work page 2013

  33. [33]

    King and D

    J. King and D. Kirkpatrick. Improved approximation for guarding simple galleries from the perimeter.Discrete & Computational Geometry, 46(2):252–269, 2011

    work page 2011

  34. [34]

    Koml´ os, J

    J. Koml´ os, J. Pach, and G. Woeginger. Almost tight bounds forϵ-nets.Discrete Comput. Geom., 7(2):163–173, March 1992. 15

    work page 1992

  35. [35]

    Y. Li, P. M. Long, and A. Srinivasan. Improved bounds on the sample complexity of learning.Journal of Computer and System Sciences, 62(3):516–527, 2001

    work page 2001

  36. [36]

    Matouˇ sek

    J. Matouˇ sek. Cutting hyperplane arrangements.Discrete & Computational Geometry, 6(3):385–406, 1991

    work page 1991

  37. [37]

    Meijer and T

    L. Meijer and T. Miltzow. Sometimes two irrational guards are needed.CoRR, abs/2212.01211, 2022

    work page arXiv 2022

  38. [38]

    Ntafos and M

    S. Ntafos and M. Tsoukalas. Optimum placement of guards.Information Sciences, 76(1–2):141 – 150, 1994

    work page 1994

  39. [39]

    O’Rourke.Art Gallery Theorems and Algorithms

    J. O’Rourke.Art Gallery Theorems and Algorithms. Oxford University Press, Inc., USA, 1987

    work page 1987

  40. [40]

    Pach and P

    J. Pach and P. K. Agarwal.Combinatorial geometry. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1995

    work page 1995

  41. [41]

    J. Renegar. On the computational complexity and geometry of the first-order theory of the reals.J. Symb. Comput., 13(3):255–352, 1992

    work page 1992

  42. [42]

    P. Valtr. Guarding galleries where no point sees a small area.Israel Journal of Mathematics, 104(1):1–16, 1998

    work page 1998

  43. [43]

    V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability & Its Applications, 16(2):264–280, 1971. 4 Alternative Approaches 4.1 Standard Greedy Approach The greedy algorithm works by iterating the following until a (1−δ)-fraction of the area of His seen from some point i...

    work page 1971