pith. sign in

arxiv: 1907.01228 · v1 · pith:YK2VKBNJnew · submitted 2019-07-02 · 💻 cs.CG

A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon

Stav Ashur , Omrit Filtser , Matthew J. Katz This is my paper

Pith reviewed 2026-05-25 10:45 UTC · model grok-4.3

classification 💻 cs.CG
keywords vertex guardingweakly visible polygonsapproximation algorithmsart gallery problemGhosh conjecturepolygon visibilitycomputational geometry
0
0 comments X

The pith

A (2+ε)-approximation algorithm exists for vertex guarding weakly visible polygons.

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

Ghosh conjectured in 1987 that vertex guarding a simple polygon admits a constant-factor approximation. This paper resolves the conjecture for the subclass of weakly visible polygons, which have an edge from which the entire polygon is visible. It constructs a (2+ε)-approximation algorithm that selects vertex guards so every point inside the polygon is seen by at least one guard. The same ratio holds for boundary guards placed anywhere except inside the distinguished edge, and a 3c-approximation is given when a boundary cover of size at most c times optimal is already known for polygons weakly visible from a chord. The work rests on a geometric study of the regions left uncovered once the boundary has been guarded.

Core claim

The paper presents a (2+ε)-approximation algorithm for the minimum vertex guard problem on weakly visible polygons. It also gives a (2+ε)-approximation for boundary guards (with one edge excluded) and a 3c-approximation for vertex guarding a polygon weakly visible from a chord when a boundary guard set of size bounded by c times optimal is supplied. All three algorithms are obtained by first placing guards to cover the boundary and then using the geometric structure of the remaining unguarded interior regions to add a bounded number of extra vertex guards that complete the cover.

What carries the argument

Geometric analysis of unguarded interior regions after boundary coverage, which admit a bounded-size augmentation to a full vertex cover.

If this is right

  • The partitioning of general polygons into weakly visible subpolygons becomes a viable route toward resolving the full conjecture.
  • The same analysis yields constant-factor approximations for the boundary-guard variant and for chord-visible polygons.
  • A good boundary cover of size c times optimal immediately gives a 3c-approximation for the chord-visible case.
  • The technique applies directly to any polygon that is weakly visible from an edge or chord.

Where Pith is reading between the lines

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

  • The result makes hierarchical decomposition into weakly visible pieces a concrete strategy for attacking the general simple-polygon case.
  • Similar region-analysis arguments may extend to other restricted polygon families such as orthogonal or monotone polygons.
  • Practical implementations could test the algorithm on large random weakly visible instances to measure observed approximation ratios.
  • If the ε term can be driven to zero, the method would yield a 2-approximation whose tightness could be checked by constructing matching lower-bound examples.

Load-bearing premise

The regions that remain unguarded after boundary coverage always admit an augmentation by a number of additional vertex guards bounded relative to the optimum.

What would settle it

A weakly visible polygon in which any boundary-first placement followed by bounded augmentation produces a guard set larger than (2+ε) times the true minimum vertex guard set.

Figures

Figures reproduced from arXiv: 1907.01228 by Matthew J. Katz, Omrit Filtser, Stav Ashur.

Figure 1
Figure 1. Figure 1: The visibility polygon of a point p ∈ P. Any vertex of P that belongs to Vis(p) is also considered a vertex of Vis(p). Consider the set of edges of Vis(p). Some of these edges are fully contained in ∂P. The edges that are not contained in ∂P are constructed edges: these are edges whose endpoints are on ∂P and whose interior is contained in the interior of P (these are the gray dotted edges in [PITH_FULL_I… view at source ↗
Figure 2
Figure 2. Figure 2: If p sees both a and b, then p sees the entire segment ab. 2.2 Pockets Consider P \ V is(p) (see [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: xy is a constructed edge, and the gray area is the set of all points of Vis(w) that lie below/above `xy. In (a) and (b) the pocket Cxy lies above `xy, and thus xy is a lower edge. In (c) and (d) the pocket Cxy lies below `xy, and xy is an upper edge. In (a) and (c) the slope of xy is positive, and in (b) and (d) it is negative. u v p y x `xy `y `x = `uv Cxy [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The gray area is Vis(p). xy is an upper edge (i.e., Cxy lies below `xy) and x is on uv, but some points of Cxy lie above `xy. P \ Cxy, ‘stepping off’ xy to one side, places us in the interior of Cxy (and ‘stepping off’ xy to the other side places us in the interior of P \ Cxy). Note that if Cxy lies above (resp. below) `xy, it does not necessarily mean that all the points of Cxy lie above (resp. below) `xy… view at source ↗
Figure 5
Figure 5. Figure 5: Two constructed edges that cross each other. [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Proof of Lemma 6. Proof. If P and S share a vertex, then we are done. Otherwise, let y be a point on ∂P that is closest to S, where the distance between a point p and S is dist(p, S) = min{||p − s|| | s ∈ S}, and let s be a point in S closest to y. We first prove that S is visible from y. If y is also on ∂S, then y clearly sees S, so assume that y is not on ∂S and that there exists a point t ∈ S that is no… view at source ↗
Figure 7
Figure 7. Figure 7: Two edges of the hole H: h1h2 and h2h3. The edge h1h2 leans on an upper edge and h1 is below h2, thus h2h3 has to lean on an upper edge such that h2 is below h3 (and not as drawn in the figure). Lemma 7. Assume that h1h2 leans on an upper edge xy, such that x is below y, x /∈ uv, and h1 is below h2. Then h2h3 also leans on an upper edge and h2 is below h3. Proof. Since xy is an upper edge, H lies below `xy… view at source ↗
Figure 8
Figure 8. Figure 8: The edges of H lean on a sequence of upper edges. This implies that every hole H leans on an upper edge with an endpoint in uv: H has at least one edge h1h2 that leans on an upper edge x1y1, and h1 is below h2. If x1 or y1 are on uv then we are done. Otherwise, by Lemma 7, the edge h2h3 also leans on an upper edge x2y2, and h2 is below h3. Again, if one of x2, y2 is on uv then we are done, otherwise by Lem… view at source ↗
Figure 9
Figure 9. Figure 9: Finding a vertex of P that guards the triangle 4xpx0 . Running time. The running time of the algorithm of [18] for finding a set of vertices G of size O(1 + ε/2)OPT that guards ∂P is O(n O(1/ε2 ) ), for any ε > 0. The set of constructed edges E can be computed in O(|G|n) time [17, 23]. Notice that Algorithm 1 only uses a subset E0 of the constructed edges, namely, those with an endpoint in uv, and by Claim… view at source ↗
Figure 10
Figure 10. Figure 10: A polygon with a concave angle at u. Removing the convexity assumption. Up to now, we have assumed that the angles at u and at v are convex. As in [18], this assumption can be easily removed. Assume, e.g., that the angle at u is concave, and let a be the first point on P’s boundary (moving clockwise from u) that lies on the x-axis (see [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The visibility polygon of a point p ∈ P. The definitions of visibility polygons, pockets, and holes, apply with no change to polygons weakly visible from a chord. However, in order for the rest of our claims to be correct, we have to update Claim 1 and Claim 3. First, we replace Claim 1 by the following claim; the proof remains unchanged. Claim 12. For any point p ∈ P, Vis(p) ∩ uv is connected. Notice tha… view at source ↗
read the original abstract

The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(\log n)$-approximation algorithm for placing as few guards as possible at vertices of a simple $n$-gon $P$, such that every point in $P$ is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date. In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a $(2+\varepsilon)$-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon $P$ is weakly visible if it has an edge $e$, such that every point in $P$ is visible from some point on $e$. We also present a $(2+\varepsilon)$-approximation algorithm for guarding a weakly visible polygon $P$, where guards may be placed anywhere on $P$'s boundary (except in the interior of the edge $e$). Finally, we present a $3c$-approximation algorithm for vertex guarding a polygon $P$ that is weakly visible from a chord, given a subset $G$ of $P$'s vertices that guards $P$'s boundary whose size is bounded by $c$ times the size of a minimum such subset. Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygon's boundary. It is plausible that our results will enable Bhattacharya et al. to complete their grand attempt to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons.

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 / 0 minor

Summary. The manuscript claims a (2+ε)-approximation algorithm for vertex guarding weakly visible polygons (WV-polygons), confirming Ghosh's conjecture for this subclass. The approach first obtains a near-optimal vertex cover of the boundary and then augments it using geometric properties of the remaining unguarded interior regions; analogous (2+ε) and 3c results are claimed for boundary guards and polygons weakly visible from a chord.

Significance. If the central analysis holds, the result would be a meaningful advance toward the general constant-factor conjecture, as WV-polygons are a natural and frequently occurring subclass and the partitioning approach cited could extend the technique. The claimed ratio is presented as independent of fitted parameters or self-referential reductions.

major comments (1)
  1. [abstract, paragraph on algorithm basis] Abstract, paragraph on algorithm basis: the claim that unguarded regions after boundary guarding always admit a bounded-size augmentation to a vertex cover is load-bearing for the (2+ε) ratio. No explicit geometric properties, bound derivation, or handling of reflex-chain configurations are supplied, so it is impossible to verify that the augmentation factor remains constant (rather than growing with n or OPT) in all WV-polygons.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the review and the identification of a key point in the abstract. We address the major comment below.

read point-by-point responses

  1. Referee: [abstract, paragraph on algorithm basis] Abstract, paragraph on algorithm basis: the claim that unguarded regions after boundary guarding always admit a bounded-size augmentation to a vertex cover is load-bearing for the (2+ε) ratio. No explicit geometric properties, bound derivation, or handling of reflex-chain configurations are supplied, so it is impossible to verify that the augmentation factor remains constant (rather than growing with n or OPT) in all WV-polygons.

    Authors: The abstract is intentionally high-level. The geometric properties of unguarded regions after boundary guarding, the derivation showing that the required augmentation is bounded by a (1+ε) factor, and the case analysis for reflex chains (including how they are partitioned and covered without depending on n or OPT) are supplied in Sections 3 and 4 of the manuscript. These sections contain the explicit arguments establishing that the overall ratio remains 2+ε. If the referee believes additional exposition or figures would improve readability of those sections, we will add them. revision: partial

Circularity Check

0 steps flagged

No circularity: independent geometric analysis supplies the constant factor

full rationale

The paper constructs a (2+ε)-approximation via an explicit algorithmic procedure that first computes a near-optimal boundary vertex cover and then augments it using a bounded-size set whose size is controlled by a fresh geometric analysis of the remaining unguarded regions in a WV-polygon. No equation or reduction in the abstract or described derivation equates the claimed ratio to a fitted parameter, a self-citation, or a renamed input; the augmentation bound is presented as the output of that analysis rather than presupposed by it. External citations (Ghosh 1987 and others) are used only for context and do not carry the constant-factor claim.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of weak visibility and on an unstated but load-bearing geometric lemma about the structure of unguarded pockets after boundary guarding.

axioms (1)
  • domain assumption A simple polygon P is weakly visible if it has an edge e such that every point in P is visible from some point on e.
    Definition invoked in the first sentence of the abstract and used to delimit the problem class.

pith-pipeline@v0.9.0 · 5897 in / 1184 out tokens · 32402 ms · 2026-05-25T10:45:53.759744+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

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

  1. [1]

    The art gallery problem is∃ R-complete

    Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The art gallery problem is∃ R-complete. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 , pages 65–73, 2018. URL: https://doi.org/10.1145/3188745.3188868, doi:10.1145/3188745.3188868. 2, 3 13

    work page doi:10.1145/3188745.3188868 2018

  2. [2]

    The art gallery theorem: its variations, applications and algorithmic aspects

    Alok Aggarwal. The art gallery theorem: its variations, applications and algorithmic aspects. 1984. 3

    work page 1984

  3. [3]

    Toussaint

    David Avis and Godfried T. Toussaint. An optimal algorithm for determining the visibility of a polygon from an edge. IEEE Trans. Computers , 30(12):910–914, 1981. URL: https://doi.org/10.1109/TC.1981.1675729, doi:10.1109/TC.1981.1675729. 3

    work page doi:10.1109/tc.1981.1675729 1981

  4. [4]

    Constant Approximation Algorithms for Guarding Simple Polygons using Vertex Guards

    Pritam Bhattacharya, Subir Kumar Ghosh, and Sudebkumar Pal. Constant approxima- tion algorithms for guarding simple polygons using vertex guards. arXiv:1712.05492,

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    Personal communication, 2018

    Pritam Bhattacharya, Subir Kumar Ghosh, Sudebkumar Pal, and Bodhayan Roy. Personal communication, 2018. 2

    work page 2018

  6. [6]

    Approximability of guarding weak visibility polygons

    Pritam Bhattacharya, Subir Kumar Ghosh, and Bodhayan Roy. Approximability of guarding weak visibility polygons. Discrete Applied Mathematics , 228:109–129, 2017. URL: https://doi.org/10.1016/j.dam.2016.12.015, doi:10.1016/j.dam.2016.12

    work page doi:10.1016/j.dam.2016.12.015 2017

  7. [7]

    An approximation algorithm for the art gallery problem

    ´Edouard Bonnet and Tillmann Miltzow. An approximation algorithm for the art gallery problem. In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia , pages 20:1–20:15, 2017. URL: https://doi.org/10. 4230/LIPIcs.SoCG.2017.20, doi:10.4230/LIPIcs.SoCG.2017.20. 2, 3

    work page doi:10.4230/lipics.socg.2017.20 2017

  8. [8]

    Heffernan, and Giri Narasimhan

    Gautam Das, Paul J. Heffernan, and Giri Narasimhan. Finding all weakly-visible chords of a polygon in linear time. Nord. J. Comput. , 1(4):433–457, 1994. 3

    work page 1994

  9. [9]

    Demaine, and Sanjay E

    Ajay Deshpande, Taejung Kim, Erik D. Demaine, and Sanjay E. Sarma. A pseudopoly- nomial time O(log n)-approximation algorithm for art gallery problems. In Algorithms and Data Structures, 10th International Workshop, WADS 2007, Halifax, Canada, Au- gust 15-17, 2007, Proceedings, pages 163–174, 2007. URL: https://doi.org/10.1007/ 978-3-540-73951-7_15 , doi:...

    work page doi:10.1007/978-3-540-73951-7 2007

  10. [10]

    Guarding galleries and terrains

    Alon Efrat and Sariel Har-Peled. Guarding galleries and terrains. Inf. Process. Lett., 100(6):238–245, 2006. URL: https://doi.org/10.1016/j.ipl.2006.05.014, doi:10. 1016/j.ipl.2006.05.014. 3

    work page doi:10.1016/j.ipl.2006.05.014 2006

  11. [11]

    Inapproximability results for guarding polygons and terrains

    Stephan Eidenbenz, Christoph Stamm, and Peter Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79–113, 2001. URL: https: //doi.org/10.1007/s00453-001-0040-8, doi:10.1007/s00453-001-0040-8. 3

    work page doi:10.1007/s00453-001-0040-8 2001

  12. [12]

    The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS

    Stephan Friedrichs, Michael Hemmer, James King, and Christiane Schmidt. The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS. JoCG, 7(1):256–284, 2016. URL: https://doi.org/10.20382/jocg.v7i1a13, doi:10.20382/jocg.v7i1a13. 12

    work page doi:10.20382/jocg.v7i1a13 2016

  13. [13]

    Approximation algorithms for art gallery problems

    Subir Kumar Ghosh. Approximation algorithms for art gallery problems. pages 429–434,

    work page

  14. [14]

    Approximation algorithms for art gallery problems in polygons

    Subir Kumar Ghosh. Approximation algorithms for art gallery problems in polygons. Discrete Applied Mathematics, 158(6):718–722, 2010. URL: https://doi.org/10.1016/ j.dam.2009.12.004, doi:10.1016/j.dam.2009.12.004. 2

    work page doi:10.1016/j.dam.2009.12.004 2010

  15. [15]

    Subir Kumar Ghosh, Anil Maheshwari, Sudebkumar Prasant Pal, Sanjeev Saluja, and C. E. Veni Madhavan. Characterizing and recognizing weak visibility polygons. Comput. Geom., 3:213–233, 1993. URL: https://doi.org/10.1016/0925-7721(93)90010-4, doi:10.1016/0925-7721(93)90010-4. 3

    work page doi:10.1016/0925-7721(93)90010-4 1993

  16. [16]

    Guarding terrains via local search

    Matt Gibson, Gaurav Kanade, Erik Krohn, and Kasturi Varadarajan. Guarding terrains via local search. Journal of Computational Geometry , 5(1):168–178, 2014. 4

    work page 2014

  17. [17]

    Joe and R

    B. Joe and R. B. Simpson. Corrections to Lee’s visibility polygon algorithm. BIT, 27(4):458–473, 1987. 10

    work page 1987

  18. [18]

    Matthew J. Katz. A PTAS for vertex guarding weakly-visible polygons — an extended abstract. CoRR, abs/1803.02160, 2018. URL: http://arxiv.org/abs/1803.02160, arXiv:1803.02160. 4, 10, 11, 12

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  19. [19]

    Detecting the weak visibility of a simple polygon and related problems

    Yan Ke. Detecting the weak visibility of a simple polygon and related problems. In Technical report. Johns Hopkins University, 1987. 3

    work page 1987

  20. [20]

    Kirkpatrick

    James King and David G. Kirkpatrick. Improved approximation for guarding simple gal- leries from the perimeter. Discrete & Computational Geometry, 46(2):252–269, 2011. URL: https://doi.org/10.1007/s00454-011-9352-x, doi:10.1007/s00454-011-9352-x. 3

    work page doi:10.1007/s00454-011-9352-x 2011

  21. [21]

    Approximate guarding of monotone and rectilinear polygons

    Erik Krohn and Bengt Nilsson. Approximate guarding of monotone and rectilinear polygons. Algorithmica, 66:564–594, 07 2013. doi:10.1007/s00453-012-9653-3. 2

    work page doi:10.1007/s00453-012-9653-3 2013

  22. [22]

    D Lee and Arthur K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory , 32:276–282, 03 1986. doi:10.1109/TIT.1986. 1057165. 3

    work page doi:10.1109/tit.1986 1986

  23. [23]

    D. T. Lee. Visibility of a simple polygon. Computer Vision, Graphics, and Image Process- ing, 22(2):207–221, 1983. URL: https://doi.org/10.1016/0734-189X(83)90065-8, doi:10.1016/0734-189X(83)90065-8. 10

    work page doi:10.1016/0734-189x(83)90065-8 1983

  24. [24]

    PTAS for geometric hitting set problems via local search

    Nabil Hassan Mustafa and Saurabh Ray. PTAS for geometric hitting set problems via local search. In Proceedings of the 25th Annual Symposium on Computational Geometry , pages 17–22. ACM, 2009. 4

    work page 2009

  25. [25]

    Art gallery theorems and algorithms , volume 57

    Joseph O’rourke. Art gallery theorems and algorithms , volume 57. Oxford University Press Oxford, 1987. 2, 3

    work page 1987

  26. [26]

    Joseph O’Rourke and Kenneth J. Supowit. Some NP-hard polygon decomposition problems. IEEE Trans. Information Theory, 29(2):181–189, 1983. URL: https://doi. org/10.1109/TIT.1983.1056648, doi:10.1109/TIT.1983.1056648. 3

    work page doi:10.1109/tit.1983.1056648 1983

  27. [27]

    An optimal algorithm for detecting weak visibility of a polygon (preliminary version)

    J¨ org-R¨ udiger Sack and Subhash Suri. An optimal algorithm for detecting weak visibility of a polygon (preliminary version). In STACS 88, 5th Annual Symposium on Theoretical 15 Aspects of Computer Science, Bordeaux, France, February 11-13, 1988, Proceedings , pages 312–321, 1988. URL: https://doi.org/10.1007/BFb0035855, doi:10.1007/ BFb0035855. 3 16

    work page doi:10.1007/bfb0035855 1988