pith. sign in

arxiv: 2403.01354 · v2 · submitted 2024-03-03 · 💻 cs.CG

An Overview of Minimum Convex Cover and Maximum Hidden Set

Reilly Browne This is my paper

Pith reviewed 2026-05-24 02:52 UTC · model grok-4.3

classification 💻 cs.CG
keywords minimum convex covermaximum hidden setsimple polygonsNP-hardnesscomputational geometryvisibilitypolygon coveringart gallery problems
0
0 comments X

The pith

It is NP-hard to determine whether a polygon has the same convex cover number as its hidden set number.

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

The paper reviews results on the minimum convex cover problem, which asks for the smallest number of convex polygons whose union covers a given polygon, and the maximum hidden set problem, which asks for the largest set of points inside the polygon such that no two are visible to each other. It proves that deciding whether these two numbers are equal for an arbitrary input polygon is NP-hard. The work supplies concrete examples where the numbers differ and applies insights from a 2023 FOCS paper to derive consequences for additional families of simple polygons.

Core claim

The central claim is that it is NP-hard to determine whether a polygon has the same convex cover number as its hidden set number. The paper supplies examples in which these quantities do not coincide and presents consequences of prior insights for other classes of simple polygons.

What carries the argument

The convex cover number (fewest convex sub-polygons whose union equals the input) and the hidden set number (largest set of mutually invisible points), together with the decision problem of whether the two numbers are equal.

Load-bearing premise

The NP-hardness reduction and the counterexamples rely on the standard definition of simple polygons used in the cited FOCS 2023 work.

What would settle it

A polynomial-time algorithm that, given any simple polygon, correctly outputs whether its convex cover number equals its hidden set number would falsify the NP-hardness claim.

Figures

Figures reproduced from arXiv: 2403.01354 by Reilly Browne.

Figure 1
Figure 1. Figure 1: The subgraphs in each of the shermer construction components. Top is a literal unit, left is a [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Orthogonal and x-monotone polygon, M which is not a homestead polygon [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Showing the remaining regions of M that haven’t been ruled out by a starting convex cover. Now we show that for each purple region Ri , after taking out the strong visibility region of Ri , the rest of M can be covered with just 2 convex pieces. By definition of strong visibility, all the points in Ri see all the points in the strong visibility region. Therefore, using any point in Ri disqualifies usage of… view at source ↗
Figure 4
Figure 4. Figure 4: Showing the size 2 convex covers of the remaining region after taking out the strong visibility [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: A polygon W which has no three collinear vertices and is not a homestead. Proof. First we show a polygon W (in [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A polygon W′ whose vertices are in general position and which is not a homestead polygon. Observing W′ (see [PITH_FULL_IMAGE:figures/full_fig_p006_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Top: Window partition of a simple polygon given in stages (Figure 3 from [17]): The windows [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Figure 1 from [5]. Arcs indicating the partial ordering of selected edges. [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Cases for placements of si and tj for edges ei = vivi+1 and ej = vjvj+1 in P. Left: Case (1), right: Case (2). In considering the hidden subset: i = i1, j = i|I| . After completing all these pairwise comparisons, we take the most restrictive constraint for each si (closest to vi+1) and ti (closest to vi). Set the point to halfway between this constraint and the respective vertex (or the midpoint of the ed… view at source ↗
Figure 11
Figure 11. Figure 11: Showing optimal hidden sets and convex covers for a monotone mountain (Left) and a convex [PITH_FULL_IMAGE:figures/full_fig_p012_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: A convex cover and a hidden set in a rocking chair polygon (green and red) and the superimposed [PITH_FULL_IMAGE:figures/full_fig_p013_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Showing the two cases for the induction. Left: Case 1, the top of the lowest rectangle is a subset [PITH_FULL_IMAGE:figures/full_fig_p014_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Case 1 for the funnel polygons. path from vn−i+1 to vi+1. See [PITH_FULL_IMAGE:figures/full_fig_p016_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Lemma 1 of [14] implies that if vi+1 does not see vn−i then either vi does not see vn−i or vn−i+1 does not see vi+1. Therefore, since in all cases we find a convex cover and hidden set of the same size, Theorem 3.9 holds. The algorithm runs in O(n) time. First, note that determining whether we are in Case 1 or Case 2 only takes O(1) time per edge in P. This is because the only way to be in Case 2 is if th… view at source ↗
Figure 16
Figure 16. Figure 16: Case 2 for funnel polygons. convex vertices here are v1, vt, and vs. Without loss of generality, we will consider the cardinalities of the chains to be such that R1 ≥ R2 ≥ R3. Funnel polygons are a subclass of pseudotriangles, where |R3| = 1. We will only consider pseudotriangles that are not funnel polygons, as Section 3.9 already gives a linear-time algorithm for funnel polygons. Theorem 3.10. For any p… view at source ↗
Figure 17
Figure 17. Figure 17: Pseudotriangle partition into funnel polygons that allow for a 2-approximation. [PITH_FULL_IMAGE:figures/full_fig_p017_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Godfried’s favorite polygon, with a convex cover of the boundary of size 3 and a hidden set of [PITH_FULL_IMAGE:figures/full_fig_p018_18.png] view at source ↗
read the original abstract

We give a review of results on the minimum convex cover and maximum hidden set problems. In addition, we give some new results. First we show that it is NP-hard to determine whether a polygon has the same convex cover number as its hidden set number. We then give some important examples in which these quantities don't always coincide. Finally, We present some consequences of insights from Browne, Kasthurirangan, Mitchell and Polishchuk [FOCS, 2023] on other classes of simple 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 / 2 minor

Summary. The manuscript reviews known results on the minimum convex cover and maximum hidden set problems for polygons. It adds three new contributions: a proof that deciding whether a polygon's convex cover number equals its hidden set number is NP-hard, concrete examples where the two numbers differ, and consequences of the authors' FOCS 2023 insights applied to additional classes of simple polygons.

Significance. If the NP-hardness reduction and separation examples hold under the standard simple-polygon model, the work would usefully establish that the two quantities are distinct even at the level of computational complexity and would supply concrete counterexamples to their equality. The overview itself synthesizes the literature and the final section extends prior results to new polygon classes; these are modest but genuine contributions when the load-bearing claims are substantiated.

major comments (1)
  1. [new results section (NP-hardness and examples)] The NP-hardness claim for deciding equality of convex cover number and hidden set number (stated in the abstract and developed in the new-results section) is presented as following from the reduction technique and polygon model of Browne et al. [FOCS 2023]. The manuscript does not contain an explicit verification that the definition of simple polygons (including any handling of holes, reflex chains, or boundary features) and the prior hardness gadgets transfer without modification; this transfer is load-bearing for both the hardness result and the separation examples.
minor comments (2)
  1. [abstract] Abstract: 'Finally, We present' contains an erroneous capital 'W' after the period.
  2. [abstract] The phrasing 'don't always coincide' in the abstract is informal for a journal submission; replace with 'do not always coincide'.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need for explicit verification in the new-results section. We address the major comment below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: [new results section (NP-hardness and examples)] The NP-hardness claim for deciding equality of convex cover number and hidden set number (stated in the abstract and developed in the new-results section) is presented as following from the reduction technique and polygon model of Browne et al. [FOCS 2023]. The manuscript does not contain an explicit verification that the definition of simple polygons (including any handling of holes, reflex chains, or boundary features) and the prior hardness gadgets transfer without modification; this transfer is load-bearing for both the hardness result and the separation examples.

    Authors: We agree that an explicit verification is warranted for clarity and to confirm load-bearing aspects. The FOCS 2023 construction produces simple polygons without holes; its gadgets rely on standard reflex chains and boundary features that are fully compatible with the simple-polygon model used throughout our manuscript. We will add a dedicated subsection (approximately one page) that (i) recalls the precise polygon definition from Browne et al., (ii) confirms absence of holes and compatibility of reflex-chain gadgets, and (iii) notes that the same constructions directly yield both the NP-hardness result and the concrete separation examples. This addition will be placed immediately after the statement of the new theorem. revision: yes

Circularity Check

1 steps flagged

Self-citation load-bearing for consequences and model transfer; new hardness result presented as independent

specific steps
  1. self citation load bearing [Abstract (final sentence) and implied in hardness section]
    "Finally, We present some consequences of insights from Browne, Kasthurirangan, Mitchell and Polishchuk [FOCS, 2023] on other classes of simple polygons."

    The consequences section is load-bearing for the paper's stated contributions yet is justified solely by citation to overlapping-author prior work; the NP-hardness reduction is also described as relying on the polygon definition and techniques from that same self-citation, creating partial dependence without independent verification of the model transfer.

full rationale

The paper presents a new NP-hardness result and counterexamples as original contributions. The final section on consequences explicitly draws from the authors' own FOCS 2023 paper, and the hardness reduction is stated to rely on the polygon model and techniques from that prior work. This creates partial self-referential dependence for part of the contribution, but the core new claim is not reduced by construction to the citation. No self-definitional, fitted-prediction, or ansatz-smuggling patterns appear. Score kept moderate per rules on non-load-bearing self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, invented entities, or non-standard axioms are stated. The work rests on the standard definition of simple polygons and the correctness of the cited FOCS 2023 results.

axioms (1)
  • domain assumption Standard model of simple polygons (possibly with holes) used in computational geometry literature
    Invoked implicitly when defining convex cover number and hidden set number.

pith-pipeline@v0.9.0 · 5592 in / 1158 out tokens · 21137 ms · 2026-05-24T02:52:28.158447+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem

    cs.CG 2026-04 unverdicted novelty 8.0

    The Nesting Bird Box Problem is ER-complete.

  2. The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem

    cs.CG 2026-04 unverdicted novelty 7.0

    The Nesting Bird Box Problem is ER-complete.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · cited by 1 Pith paper

  1. [1]

    Covering polygons is even harder

    Mikkel Abrahamsen. Covering polygons is even harder. 2021 IEEE 62nd Annual Symposium on Foun- dations of Computer Science (FOCS) , pages 375–386, 2022

    work page 2021

  2. [2]

    Constructing Concise Convex Covers via Clique Covers

    Mikkel Abrahamsen, William Bille Meyling, and Andr´ e Nusser. Constructing Concise Convex Covers via Clique Covers. In Erin W. Chambers and Joachim Gudmundsson, editors, 39th International Sym- posium on Computational Geometry (SoCG 2023) , volume 258 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 66:1–66:9, Dagstuhl, Germany, 2023. ...

    work page 2023

  3. [3]

    A 1/4-approximation algorithm for the maximum hidden vertex set problem in simple polygons

    Carlos Alegr´ ıa, Pritam Bhattacharya, and Subir Kumar Ghosh. A 1/4-approximation algorithm for the maximum hidden vertex set problem in simple polygons. In European Workshop on Computational Geometry, 2019

    work page 2019

  4. [4]

    Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford

    Jan Van Den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 503–514, 2023

    work page 2023

  5. [5]

    Browne, P

    R. Browne, P. Kasthurirangan, J. B. Mitchell, and V. Polishchuk. Constant-factor approximation algorithms for convex cover and hidden set in a simple polygon. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1357–1365, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society

    work page 2023

  6. [6]

    Convex cover and hidden set in funnel polygons, 2023

    Reilly Browne. Convex cover and hidden set in funnel polygons, 2023

    work page 2023

  7. [7]

    Collapsing the hidden-set convex-cover inequality

    Reilly Browne and Eric Chiu. Collapsing the hidden-set convex-cover inequality. In Proceedings of the 38th Computational Geometry Young Researchers Forum (CG:YRF 2022) , pages 27–32. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2022

    work page 2022

  8. [8]

    Culberson and R.A

    J.C. Culberson and R.A. Reckhow. Covering polygons is hard. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science , pages 601–611, 1988

    work page 1988

  9. [9]

    R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math. , 51(1):161–166, 1950

    work page 1950

  10. [10]

    Inapproximability of finding maximum hidden sets on polygons and terrains

    Stephan Eidenbenz. Inapproximability of finding maximum hidden sets on polygons and terrains. Computational Geometry, 21(3):139–153, 2002

    work page 2002

  11. [11]

    Eidenbenz and Peter Widmayer

    Stephan J. Eidenbenz and Peter Widmayer. An approximation algorithm for minimum convex cover with logarithmic performance guarantee. SIAM Journal on Computing , 32(3):654–670, 2003

    work page 2003

  12. [12]

    D. S. Franzblau. Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles. SIAM Journal on Discrete Mathematics , 2(3):307–321, 1989. 19

    work page 1989

  13. [13]

    Gella and Rosalio G

    Frederick S. Gella and Rosalio G. Artes. Clique cover of graphs. Applied mathematical sciences, 8:4301– 4307, 2014

    work page 2014

  14. [14]

    Veni Madha- van

    Subir Kumar Ghosh, Anil Maheshwari, Sudebkumar Prasant Pal, Sanjeev Saluja, and C.E. Veni Madha- van. Characterizing and recognizing weak visibility polygons. Computational Geometry, 3(4):213–233, 1993

    work page 1993

  15. [15]

    Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Endre Tarjan

    Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Endre Tarjan. Linear- time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorith- mica, 2:209–233, 1987

    work page 1987

  16. [16]

    Lee and F

    D. Lee and F. Preparata. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM (JACM), 26:415–421, 07 1979

    work page 1979

  17. [17]

    Joseph S. B. Mitchell, Valentin Polishchuk, and Mikko Sysikaski. Minimum-link paths revisited. Com- putational Geometry, 47(6):651–667, 2014. Special issue on EuroCG’11

    work page 2014

  18. [18]

    T. Shermer. Hiding people in polygons. Computing, 42(2-3):109–131, 1989

    work page 1989

  19. [19]

    A linear time algorithm for minimum link paths inside a simple polygon

    Subhash Suri. A linear time algorithm for minimum link paths inside a simple polygon. Computer Vision, Graphics, and Image Processing , 35(1):99–110, 1986. 20

    work page 1986