Pith. sign in

REVIEW 4 major objections 5 minor 19 references

Minimum Membership Geometric Set Cover in the Continuous Setting

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For continuous point sets, low-membership covers by unit squares, hypercubes, disks, and convex polygons can be built quickly with sizes within constant or 2^{d-1} factors of optimal.

desk verdict The 2D square cover result is clean and the continuous setting is well motivated, but the paper is uneven: the hypercube lemma is actually correct (contra the stress-test), while the NP-hardness and tiling proofs need real work. read the letter →

arxiv 2506.00272 v1 pith:TEL4AZOF submitted 2025-05-30 cs.CG

Sathish Govindarajan , Mayuresh Patle , Siddhartha Sarkar This is my paper
classification cs.CG MSC 68U0568W2552C15
keywords minimummembershipgeometricsetcovercontinuoussettingplyunitsquarediskconvexpolygonapproximationalgorithmNP-hardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies the continuous minimum-membership geometric set cover problem: given n points and a shape t, place translated copies of t so that every point is covered while minimizing the maximum number of copies containing any one point, called the membership or ply. It shows that in the continuous setting this problem becomes tractable through a simple sweep that separates points into unit-thick strips. For unit squares it produces a 1-membership cover of size at most twice the optimal; for d-dimensional unit hypercubes the factor is $2^{{d-1}}$; for unit disks a 2-membership cover exists with size at most 7 times optimal; and for convex m-gons a 4-membership cover can be found in O(n log n + mn) time. The paper also characterizes when a 1-membership cover always exists, proving it happens exactly when the shape tiles the plane, and shows that computing the minimum number of non-overlapping unit squares needed to cover points is NP-hard. These results matter because continuous placement is the realistic form of coverage problems in wireless networks, where low membership keeps interference low.

What carries the argument

The central object is the 'Separate' sweep: sort points along one coordinate and, for each as-yet-uncovered point, place a unit interval with that point as its left endpoint, producing non-overlapping intervals and dividing the point set into unit-thick vertical strips. Alternating odd- and even-indexed strips support a charging argument, since one shape cannot cover points lying two strips apart. In higher dimensions this becomes a wall decomposition, where each unit-thick slab is handled recursively. For disks, a grid of squares gives a lattice of unit disks in which only horizontally or vertically adjacent disks can cross, bounding the ply by 2. For polygons, homothetic inner and outer rectangle pairs control the ply while keeping the fast square-cover algorithm available.

What would settle it

Construct a small finite point set inside a unit-thick wall in $R^{3}$, compute the minimum number of disjoint unit cubes covering it and the minimum number of disjoint unit squares covering its orthogonal projection; if any instance gives different counts, Lemma 3, and with it the $2^{{d-1}}$ approximation factor for d at least 3, fails as stated.

Watch

Extended reading notes

Core claim

The central claim is that the continuous minimum-membership geometric set cover problem admits efficient approximation algorithms for several natural shapes. The 'Separate' greedy algorithm covers points on a line with disjoint unit intervals optimally; applying it first to x-coordinates and then to y-coordinates inside each generated strip yields a 1-ply unit-square cover of size at most twice the optimal 1-ply cover. The same recursive coordinate separation in d dimensions gives a 1-ply unit-hypercube cover of size at most $2^{{d-1}}$ times optimal in O(d n log n) time. For unit disks, drawing circumcircles around the squares of a fine grid produces a 2-ply disk cover of size at most 7 times the optimal 2-ply cover. For convex polygons, an approximating pair of inner and outer rectangles transfers the square-cover guarantee to a 4-ply cover of translated copies of the polygon.

Load-bearing premise

The proof of Lemma 3 assumes that, for points inside one unit-thick wall, the fewest disjoint unit d-cubes needed equals the fewest disjoint unit (d-1)-cubes needed for the same points' orthogonal projections, and this equality is asserted without proof even though cubes in different layers can overlap in projection while still being disjoint in space.

Editorial extensions

If this is right

  • For every finite point set in R^d, a 1-ply unit-hypercube cover of size at most 2^{d-1} times optimal can be computed in O(d n log n) time.
  • Every finite point set in the plane admits a 2-ply unit-disk cover, and one of size at most 7 times the optimal 2-ply cover can be constructed explicitly.
  • Any convex polygon with m vertices admits a 4-ply cover by translated copies, computable in O(n log n + nm) time.
  • When the covering object tiles the plane, a 1-membership cover exists for any point set; when it does not tile the plane, there is a point set with no 1-membership cover.
  • Finding the minimum number of non-overlapping unit squares that cover a given point set is NP-hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step the paper does not take is to verify the wall-versus-projection equality used in Lemma 3; if it fails in dimension three or higher, the d-dimensional approximation factor would need a different charging argument.
  • The odd/even strip charging is not obviously limited to squares and hypercubes, so a unified treatment of continuous low-membership cover for centrally symmetric convex bodies may be within reach.
  • The NP-hardness result for non-overlapping unit squares suggests that exact optimization of minimum-ply covers is unlikely to be tractable in general, making approximation the right target, which this paper supplies.
  • A concrete testable extension would be to compute optimal 1-ply covers for small random point sets inside a unit-thick wall in R^3 and compare the count with the optimal 1-ply cover of their orthogonal projections, directly probing the Lemma 3 assumption.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies the continuous version of Minimum-Membership Geometric Set Cover (MMGSC), in which translated copies of a fixed object must cover a finite point set while minimizing the maximum number of covering objects that contain any input point. The main advertised results are: an O(n log n) algorithm producing a 1-ply unit-square cover of size at most twice the optimum; a d-dimensional generalization producing a 1-ply unit-hypercube cover of size at most 2^{d-1} times the optimum; an NP-hardness proof for the minimum-size 1-ply unit-square cover problem; a characterization of objects for which 1-ply covers always exist; a 2-ply unit-disk cover with a 7-approximation guarantee; and a 4-ply convex-polygon cover algorithm.

Significance. If the results were fully established, the paper would contribute useful first approximation algorithms for continuous MMGSC, a problem that is well motivated by interference minimization in geometric networks. The interval and 2D square sections are clean, self-contained, and appear correct. However, the d-dimensional theorem rests on a lemma that is false, and the NP-hardness proof is a sketch that leaves the central gadget undefined. The disk and polygon results are plausible but are argued too tersely. The 2D square and interval material is publishable, but the paper as a whole advertises unsupported results.

major comments (4)
  1. [§2.3, Lemma 3] Lemma 3 is false as stated. For d=3, take P = {(0,0,0), (1,1,0.5), (2,0,1), (1,-1,0.6)}, all lying in the wall R^2 × [0,1]. Their projections to R^2 are A=(0,0), B=(1,1), C=(2,0), D=(1,-1). A 1-ply planar unit-square cover of these four projections needs three squares: the only unit square that can contain A and B is [0,1]^2, the only one that can contain C and D is [1,2]×[-1,0], and these two squares intersect at (1,0); similarly the pairing (A,D) with (B,C) intersects at (1,0), and no unit square contains three of the points, so two disjoint squares are impossible. Yet the two unit cubes [0,1]×[0,1]×[-0.5,0.5] and [1,2]×[-1,0]×[0.51,1.51] are disjoint and cover P. Thus the optimal d-dimensional 1-ply cover of the wall points has size 2, while the optimal (d-1)-dimensional 1-ply cover of their projections has size 3. The equality asserted in Lemma 3 fails, so the induction proof of Theorem 3 is invalid.
  2. [§2.4, Theorem 4] The NP-hardness proof is a sketch rather than a reduction. The guiding unit squares, the placement of the variable and clause points, and the connection between variable and clause gadgets are described qualitatively; no coordinates or exact placement rules are given. The central clause point p_alpha is placed 'in a specific way, to be made precise shortly,' and the two bulleted properties of the central clause squares are asserted rather than proved. The budget argument in the reverse direction also relies on unproved claims that each variable has exactly two feasible square patterns and that an unsatisfied clause must force all three central clause squares. As written, the reduction is not verifiable and does not establish NP-hardness.
  3. [§3, Theorem 5] The theorem is false as stated. If t is a non-tiling object and P is a one-point set, a 1-ply cover trivially exists, so the statement 'a 1-ply cover exists if and only if t is a tiling object' cannot hold for an arbitrary given P. The intended statement must quantify over all finite point sets or over the existence of a hard point set. The proof of the only-if direction also needs justification: it assumes a packing with a minimal hole of size s and then uses a grid of cell size smaller than s, but it is not shown that every finite 1-ply cover of that grid would correspond to a full packing whose smallest hole has size at least s. The expansion-and-shrinking construction in the forward direction similarly needs a precise argument that a shift of a tiling can keep all input points at distance at least delta from the tile boundaries.
  4. [§4, Lemma 5] The 2-ply disk cover argument needs a rigorous proof rather than an appeal to Figure 4. The claim that the circumcircles form a grid in which only horizontal and vertical neighbors cross, and that every unit disk intersects at most 7 disks of the cover, is load-bearing for the 7-approximation but is not proven. Since the construction uses squares of side 1/√2, the diagonal distance between circle centers is exactly 1 when the separating gaps vanish; the role of the positive gaps produced by the Separate algorithm must be made quantitative to rule out higher ply at grid vertices. Please provide a complete argument or a precise configuration with explicit gap parameters.
minor comments (5)
  1. [Abstract] There are typographical issues such as 'an 1-membership cover' and 'fixed-sized hyperboxes'; these should be corrected to grammatical phrasing.
  2. [§2.1, Lemma 1] The stay-ahead proof can be clarified: the claim that s_i covers all points covered by opt_i should be stated more formally, including why the contradiction 'opt_i contains p and ends strictly after s_i' is impossible for unit intervals.
  3. [§2.2, Theorem 2] The notation in the running-time calculation, including the rendered sum 'P i∈[k] ni = n', should be fixed, and the sentence 'Since there is a gap between Vi and Vi+1, as well as between Vi+1 and Vi+2' should be rephrased because the strips of the same parity are separated by at least one full intervening strip.
  4. [§2.3, Definition 4] The definition of 'd-dimensional projection of a point' is confusing; it should say that the projection keeps the first d coordinates and discards the remaining coordinates.
  5. [§5, Theorem 6] The convex-polygon section does not state an approximation factor; it only guarantees a 4-ply cover. If no size approximation is claimed, this should be stated explicitly to avoid confusion with the other results.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the paper's algorithms and approximation bounds are self-contained, with Lemma 3 as an unproved geometric gap rather than a circular step.

full rationale

The paper's main claims are constructive: the interval greedy algorithm is proved optimal by a stay-ahead argument; the unit-square cover is separated into vertical strips and bounded by an optimal cover of the same class; the disk and polygon constructions are based on packing and homothetic-approximation arguments. No parameter is fitted to data, and no prediction is simply renamed input. The one weak point is Lemma 3, which asserts equality between the optimal d-dimensional 1-ply cover in a wall and the optimal (d-1)-dimensional 1-ply cover of projections; this is an unproved and possibly false geometric assertion, but it is not circular because it is not defined in terms of the theorem's conclusion and is not justified by self-citation. All external citations (PLANAR3SAT hardness, homothetic rectangle approximation, non-existence of disjoint unit disk covers) are independent of the paper's own results. Therefore the derivation chain is not circular; the unsupported wall-projection equality is a correctness concern, not a circularity finding.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted constants appear in the paper. The main results rest on standard cited facts (PLANAR3SAT hardness, homothetic rectangle approximation) and on two unproved geometric assumptions: the wall-projection equality in Lemma 3, and the existence of a positive minimal hole size for packings of non-tiling objects. These assumptions, rather than any tuned parameter, drive the correctness risk of the d-dimensional, tiling, and NP-hardness claims.

assumptions (4)
  • standard math PLANAR3SAT is NP-hard (Lichtenstein 1982)
    Used as the source problem for the NP-hardness reduction in Section 2.4.
  • ad hoc to paper For points within a single d-dimensional wall, the size of the smallest d-dimensional 1-ply hypercube cover equals the size of the smallest (d-1)-dimensional 1-ply hypercube cover for the projected points.
    Assumed without proof in Lemma 3 to obtain the 2^{d-1} approximation. This equality is not obvious because d-cubes in a wall can be disjoint while their projections overlap.
  • domain assumption Every non-tiling object has a packing whose smallest hole has a positive size s.
    Used in the 'only if' direction of Theorem 5. Not proven; if packings can have arbitrarily small holes, the grid argument fails.
  • domain assumption For any convex shape C there is a homothetic rectangle pair (r,R) with r ⊆ C ⊆ R and lambda(r,R) <= 2, computable in O(log^2 m) time.
    Taken from Cheong et al. and Lassak; used in Section 5 to build 4-ply convex polygon covers.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum Membership Geometric Set Cover in the Continuous Setting." pith.science (2026). https://pith.science/paper/TEL4AZOF

@misc{pith2026250600272,
  author       = {Pith},
  title        = {Pith review of: Minimum Membership Geometric Set Cover in the Continuous Setting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TEL4AZOF}},
  note         = {Machine review of arXiv:2506.00272}
}
abstract

We study the minimum membership geometric set cover, i.e., MMGSC problem [SoCG, 2023] in the continuous setting. In this problem, the input consists of a set $P$ of $n$ points in $\mathbb{R}^{2}$, and a geometric object $t$, the goal is to find a set $\mathcal{S}$ of translated copies of the geometric object $t$ that covers all the points in $P$ while minimizing $\mathsf{memb}(P, \mathcal{S})$, where $\mathsf{memb}(P, \mathcal{S})=\max_{p\in P}|\{s\in \mathcal{S}: p\in s\}|$. For unit squares, we present a simple $O(n\log n)$ time algorithm that outputs a $1$-membership cover. We show that the size of our solution is at most twice that of an optimal solution. We establish the NP-hardness on the problem of computing the minimum number of non-overlapping unit squares required to cover a given set of points. This algorithm also generalizes to fixed-sized hyperboxes in $d$-dimensional space, where an $1$-membership cover with size at most $2^{d-1}$ times the size of a minimum-sized $1$-membership cover is computed in $O(dn\log n)$ time. Additionally, we characterize a class of objects for which a $1$-membership cover always exists. For unit disks, we prove that a $2$-membership cover exists for any point set, and the size of the cover is at most $7$ times that of the optimal cover. For arbitrary convex polygons with $m$ vertices, we present an algorithm that outputs a $4$-membership cover in $O(n\log n + nm)$ time.

Figures

Figures reproduced from arXiv: 2506.00272 by the authors.

Figure 1
Figure 1. (a) Partitioning into vertical strips. (b) 1-ply unit square cover. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The left figure shows a planar embedding of a [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Depicting a clause (¬xi ∨ ¬xj ∨ xk). The variable gadgets for xi , xj , xk are drawn from left to right; xi appears in its positive form in some other clause; xj appears only in α; and xk appears in its negative form in some other clause. and three vertical chains of guiding unit squares. These squares are called clause squares. See [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Illustration of a 2-ply unit disk cover configuration. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Illustrations for Convex Polygon Cover: (a) Approximating pair ( [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    In: Canadian Conference on Computational Geometry (2012), https://api.semanticscholar.org/CorpusID:16280099

    Aloupis, G., Hearn, R.A., Iwasawa, H., Uehara, R.: Covering points with dis- joint unit disks. In: Canadian Conference on Computational Geometry (2012), https://api.semanticscholar.org/CorpusID:16280099

    work page 2012

  2. [2]

    In: International Symposium on Computational Geom- etry (2023)

    Bandyapadhyay, S., Lochet, W., Saurabh, S., Xue, J.: Minimum-membership geo- metric set cover, revisited. In: International Symposium on Computational Geom- etry (2023)

    work page 2023

  3. [3]

    Computational Geometry 94, 101712 (2021)

    Biedl, T., Biniaz, A., Lubiw, A.: Minimum ply covering of points with disks and squares. Computational Geometry 94, 101712 (2021)

    work page 2021

  4. [4]

    In: Pro- ceedings of the 32nd Canadian Conference on Computational Geometry

    Biniaz, A., Lin, Z.: Minimum ply covering of points with convex shapes. In: Pro- ceedings of the 32nd Canadian Conference on Computational Geometry. pp. 2–5 (2020)

    work page 2020

  5. [5]

    Computational Geometry 60, 8–18 (2017), the Twenty-Seventh Canadian Conference on Computational Geometry August 2015

    Biniaz, A., Liu, P., Maheshwari, A., Smid, M.: Approximation algorithms for the unit disk cover problem in 2d and 3d. Computational Geometry 60, 8–18 (2017), the Twenty-Seventh Canadian Conference on Computational Geometry August 2015

    work page 2017

  6. [6]

    Discrete & Computational Geometry 14(1), 463 – 479 (1995), cited by: 392; All Open Access, Bronze Open Access

    Br¨ onnimann, H., Goodrich, M.: Almost optimal set covers in finite vc-dimension. Discrete & Computational Geometry 14(1), 463 – 479 (1995), cited by: 392; All Open Access, Bronze Open Access

    work page 1995

  7. [7]

    Computational Geometry 10(2), 77–87 (1998)

    Cheong, O., Fuchs, U., Rote, G., Welzl, E.: Approximation of convex figures by pairs of rectangles. Computational Geometry 10(2), 77–87 (1998)

    work page 1998

  8. [8]

    SIAM Journal on Com- puting 38(4), 1464–1483 (2008)

    Demaine, E.D., Feige, U., Hajiaghayi, M., Salavatipour, M.R.: Combination can be hard: Approximability of the unique coverage problem. SIAM Journal on Com- puting 38(4), 1464–1483 (2008)

    work page 2008

Show all 19 references
  1. [9]

    In: W ALCOM: Algorithms and Computation: 17th International Con- ference and Workshops, W ALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings

    Durocher, S., Keil, J.M., Mondal, D.: Minimum ply covering of points with unit squares. In: W ALCOM: Algorithms and Computation: 17th International Con- ference and Workshops, W ALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings. p. 23–35. Springer-Verlag, Berlin, Hei...

    2023

  2. [10]

    In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algo- rithms

    Erlebach, T., van Leeuwen, E.J.: Approximating geometric coverage problems. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algo- rithms. p. 1267–1276. SODA ’08, Society for Industrial and Applied Mathematics, USA (2008)

    2008

  3. [11]

    Lecture Notes in Computer Science (includ- ing subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioin- formatics) 4508 LNCS, 317 – 326 (2007)

    Fu, B., Chen, Z., Abdelguerfi, M.: An almost linear time 2.8334-approximation al- gorithm for the disc covering problem. Lecture Notes in Computer Science (includ- ing subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioin- formatics) 4508 LNCS, 317 – 326 (2007)

    2007

  4. [12]

    In: Hong, S.H., Nishizeki, T., Quan, W

    Goaoc, X., Kratochv ´ ıl, J., Okamoto, Y., Shin, C.S., Wolff, A.: Moving vertices to make drawings plane. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) Graph Drawing. pp. 101–112. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)

    2008

  5. [13]

    Information Processing Letters 40(4), 181–188 (1991)

    Gonzalez, T.F.: Covering a set of points in multidimensional space. Information Processing Letters 40(4), 181–188 (1991)

    1991

  6. [14]

    In: Kalyanasundaram, S., Maheshwari, A

    Govindarajan, S., Sarkar, S.: Improved algorithms for minimum-membership geo- metric set cover. In: Kalyanasundaram, S., Maheshwari, A. (eds.) Algorithms and Discrete Applied Mathematics. pp. 103–116. Springer Nature Switzerland, Cham (2024)

    2024

  7. [15]

    Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and vlsi. J. ACM 32(1), 130–136 (jan 1985)

    1985

  8. [16]

    SIAM Journal on Discrete Mathematics 5(3), 422–427 (1992)

    Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM Journal on Discrete Mathematics 5(3), 422–427 (1992)

    1992

  9. [17]

    Geometriae Dedicata 47, 111–117 (01 1993)

    Lassak, M.: Approximation of convex bodies by rectangles. Geometriae Dedicata 47, 111–117 (01 1993). https://doi.org/10.1007/BF01263495

    1993 doi

  10. [18]

    van Leeuwen, E.J.: Optimization and approximation on systems of geometric ob- jects. Ph.D. thesis, University of Amsterdam (2009)

    2009

  11. [19]

    Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (May 1982)

    1982

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.