pith. machine review for the scientific record. sign in

arxiv: 2605.14499 · v1 · submitted 2026-05-14 · 💻 cs.CG · cs.DS

Recognition: no theorem link

Hitting Axis-Parallel Segments with Weighted Points

Rajiv Raman , Siddhartha Sarkar , Jatin Yadav
Authors on Pith no claims yet

Pith reviewed 2026-05-15 01:10 UTC · model grok-4.3

classification 💻 cs.CG cs.DS
keywords geometric hitting setapproximation algorithmsLP roundingaxis-parallel segmentsrandomized algorithmscomputational geometry
0
0 comments X

The pith

An LP-rounding algorithm achieves a randomized (1 + 2/e)-approximation for hitting weighted axis-parallel segments, breaking the factor-2 barrier.

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

The input consists of weighted points and a collection of horizontal and vertical segments; the task is to pick a minimum-weight subset of points that intersects every segment. A naive split into horizontal and vertical subproblems yields only a factor-2 approximation. The paper introduces an LP-rounding procedure that systematically rounds points lying on horizontal lines and then solves the residual vertical sub-instances exactly. This combination produces the improved randomized (1 + 2/e) guarantee for weighted instances and a sharper (1 + 1/(e-1)) guarantee when weights are uniform. The same method also tightens the approximation for the variant in which one family consists of infinite lines and establishes APX-hardness for that case.

Core claim

We present an LP-rounding algorithm that breaks the factor-2 barrier. For the weighted problem, we obtain a randomized (1+2/e)-approximation by combining systematic rounding on horizontal lines with an exact repair step on residual vertical sub-instances. In the unweighted case, a sharper analysis gives a (1+1/(e-1))-approximation. When one of the sub-instances consists of lines instead of line segments, we improve the result to an approximation factor of 1+1/e and show that the problem is APX-hard.

What carries the argument

LP relaxation of the hitting-set instance whose fractional solution is rounded by systematic selection on each horizontal line followed by an exact optimal repair of the remaining vertical sub-instances.

If this is right

  • Weighted instances admit a randomized (1 + 2/e)-approximation.
  • Unweighted instances admit a (1 + 1/(e-1))-approximation.
  • The variant with infinite lines in one orientation admits a 1 + 1/e approximation and is APX-hard.
  • The same rounding-plus-repair technique extends to d orientations and yields PTASes for bounded-complexity unweighted subclasses.

Where Pith is reading between the lines

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

  • The horizontal-then-vertical repair pattern may extend to other geometric covering problems that admit a natural orientation decomposition.
  • Whether APX-hardness carries over from the mixed line-segment case to the pure segment case is left open by the analysis.
  • The specific constants involving e suggest that a still tighter global rounding scheme without the repair step might exist.

Load-bearing premise

The LP relaxation admits an efficient solution whose fractional optimum is within a constant factor of the integral optimum, and the rounding analysis holds for arbitrary axis-parallel positions.

What would settle it

An explicit set of weighted points and axis-parallel segments on which every integral hitting set has total weight strictly larger than (1 + 2/e) times the value of the LP optimum.

Figures

Figures reproduced from arXiv: 2605.14499 by Jatin Yadav, Rajiv Raman, Siddhartha Sarkar.

Figure 1
Figure 1. Figure 1: An integrality-gap instance for unweighted axis-parallel segment hitting. Segments are [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A hitting-set instance corresponding to ϕ = (x1 ∨ x2) ∧ (¯x1 ∨ x¯3) ∧ (x2 ∨ x¯3). If the selected points of H for the variable gadget Gi are consistent, that is, all are red or all are green, then we replace the points of H used inside Gi by the corresponding canonical optimum set of bi red or green points. This does not increase the number of points. If the selected literal points are inconsistent, then H… view at source ↗
Figure 3
Figure 3. Figure 3: Two vertex gadgets for vs, vt ∈ V in the dual construction, where (vs, vt) ∈ E. For each vertex vt incident to edges ei , ej , ek, i < j < k, the points wt , yt lie on L1 and xt , zt lie on L2. The three solid lines encode the sets {wt , ai}, {xt , yt , aj}, and {zt , ak}; the dashed magenta lines encode the non-edge sets {wt , xt} and {yt , zt}. It follows that the constructed dual finite line-cover insta… view at source ↗
read the original abstract

We study a geometric hitting-set problem in which the input consists of a set $P$ of weighted points and a family $S=H\cup V$ of axis-parallel segments in the plane. The goal is to select a minimum-weight subset of $P$ that hits every segment in $S$. Even restricted geometric hitting-set problems are known to be computationally hard, and for axis-parallel segments the standard decomposition into horizontal and vertical sub-instances yields only a simple factor-$2$ approximation. We present an LP-rounding algorithm that breaks the factor-2 barrier. For the weighted problem, we obtain a randomized $(1+2/e)$-approximation by combining systematic rounding on horizontal lines with an exact repair step on residual vertical sub-instances. In the unweighted case, a sharper analysis gives a $(1+1/(e-1))$-approximation. Finally, we consider the case where one of the sub-instances consists of lines instead of line segments, a problem considered by Fekete et al. (Geometric Hitting Set for Segments of Few Orientations, Theor. Comp. Sys., 62 (2) 2018),. In this case, we improve their result to obtain an approximation factor of $1+1/e$ and show that the problem is APX-hard. We also present algorithms for the generalization to $d$ orientations, as well as PTASes for bounded-complexity subclasses of the unweighted Hitting Set problem.

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 studies the minimum-weight hitting-set problem for axis-parallel segments using weighted points. It decomposes the instance into horizontal and vertical subproblems and presents an LP-rounding algorithm that achieves a randomized (1+2/e)-approximation for the weighted case via systematic rounding on horizontal lines followed by an exact repair step on residual vertical sub-instances. Sharper (1+1/(e-1)) bounds are given for the unweighted case; the paper also improves the approximation to 1+1/e when one sub-instance consists of lines (with an accompanying APX-hardness proof), gives algorithms for d orientations, and supplies PTASes for bounded-complexity subclasses.

Significance. If the rounding analysis is correct, the result meaningfully improves on the trivial factor-2 approximation obtained by independent horizontal/vertical decompositions, which is a standard baseline for this geometric hitting-set variant. The combination of randomized systematic rounding with an exact repair step is a clean algorithmic idea that could extend to other geometric set-cover problems. The APX-hardness result and PTASes for restricted cases further strengthen the contribution by delineating approximability.

major comments (1)
  1. [§4] §4 (analysis of the two-phase LP-rounding algorithm): the expectation bound of 1+2/e must be supported by an explicit cross-phase charging argument. Because a point selected during the exact vertical repair may already have contributed to the horizontal rounding expectation, simply adding the repair cost to the horizontal expectation risks overcounting; the proof must show how the already-accounted fractional mass is subtracted or how linearity of expectation is applied across both phases without inflating the total.
minor comments (2)
  1. [Abstract] The abstract and introduction use the term 'systematic rounding' without a one-sentence definition or forward reference; a brief parenthetical description would aid readers.
  2. [Figure 1] Figure 1 (or the first illustrative figure) would benefit from explicit labels indicating which segments are handled in the horizontal rounding phase versus the vertical repair phase.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comment on the analysis. We address the major point below and will revise the manuscript to make the cross-phase accounting fully explicit.

read point-by-point responses

  1. Referee: [§4] §4 (analysis of the two-phase LP-rounding algorithm): the expectation bound of 1+2/e must be supported by an explicit cross-phase charging argument. Because a point selected during the exact vertical repair may already have contributed to the horizontal rounding expectation, simply adding the repair cost to the horizontal expectation risks overcounting; the proof must show how the already-accounted fractional mass is subtracted or how linearity of expectation is applied across both phases without inflating the total.

    Authors: We agree that an explicit cross-phase charging argument improves clarity. The current proof first bounds the expected cost of the randomized horizontal rounding phase by (1 + 1/e) times the horizontal LP value via standard pipage-style analysis on each line. The subsequent exact repair on residual vertical segments is solved optimally (via dynamic programming on the line arrangement). To handle possible overlap, we apply linearity of expectation to per-point indicator variables across both phases while charging each repair point only against the residual fractional mass on its vertical line after subtracting the coverage probability already contributed by the horizontal phase. This yields a total expectation of at most (1 + 2/e) OPT without inflation. We will insert a dedicated charging lemma and expanded calculation in the revised Section 4. revision: yes

Circularity Check

0 steps flagged

No circularity: approximation ratios derived from independent probabilistic analysis

full rationale

The paper presents an LP-rounding algorithm whose (1+2/e) and (1+1/(e-1)) ratios are obtained by direct expectation calculations on the described systematic horizontal rounding plus exact vertical repair procedure. No step reduces by construction to a fitted parameter, self-referential definition, or load-bearing self-citation; the cited prior work (Fekete et al.) is external and the analysis is self-contained against the input LP and geometric assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard LP duality and probabilistic rounding arguments from approximation-algorithm literature; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Existence of an optimal fractional solution to the natural hitting-set LP that can be rounded while preserving the stated expectation bounds.
    Invoked in the description of the LP-rounding procedure.

pith-pipeline@v0.9.0 · 5567 in / 1247 out tokens · 60386 ms · 2026-05-15T01:10:53.806777+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

34 extracted references · 34 canonical work pages

  1. [1]

    Approximationschemesforindependent set and sparse subsets of polygons.Journal of the ACM, 66(4):29:1–29:40, 2019

    AnnaAdamaszek, SarielHar-Peled, andAndreasWiese. Approximationschemesforindependent set and sparse subsets of polygons.Journal of the ACM, 66(4):29:1–29:40, 2019

    work page 2019

  2. [2]

    A non-linear lower bound for planar epsilon-nets.Discret

    Noga Alon. A non-linear lower bound for planar epsilon-nets.Discret. Comput. Geom., 47(2):235–244, 2012

    work page 2012

  3. [3]

    Small-sizeϵ-nets for axis-parallel rectangles and boxes.SIAM J

    Boris Aronov, Esther Ezra, and Micha Sharir. Small-sizeϵ-nets for axis-parallel rectangles and boxes.SIAM J. Comput., 39(7):3248–3282, 2010

    work page 2010

  4. [4]

    Katz, Gila Morgenstern, and Yelena Yuditsky

    Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation schemes for covering and packing. In Subir Kumar Ghosh and Takeshi Tokuyama, editors,WAL- COM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, volume 7748 ofLecture Notes in Computer Science, pages 89...

    work page 2013

  5. [5]

    On the number of points in general position in the plane

    Jozsef Balogh and Jozsef Solymosi. On the number of points in general position in the plane. Discrete Analysis, (16):1–20, 2018

    work page 2018

  6. [6]

    Geometric optimization parameterized by piercing complexity

    Aritra Banik, Rajiv Raman, and Saurabh Ray. Geometric optimization parameterized by piercing complexity. InEATCS International Colloquium on Automata, Languages, and Programming (ICALP) 2026. to appear. 17

    work page 2026

  7. [7]

    Packing and covering with non-piercing regions.Discrete & Computational Geometry, 2018

    Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions.Discrete & Computational Geometry, 2018

    work page 2018

  8. [8]

    Goodrich

    Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(4):463–479, 1995

    work page 1995

  9. [9]

    On the independence number of intersection graphs of axis-parallel segments.J

    Marco Caoduro, Jana Cslovjecsek, Michal Pilipczuk, and Karol Węgrzycki. On the independence number of intersection graphs of axis-parallel segments.J. Comput. Geom., 14(1):144–156, 2023

    work page 2023

  10. [10]

    Chan and Elyot Grant

    Timothy M. Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and covering problems. volume 47, pages 112–124, 2014

    work page 2014

  11. [11]

    Chan and Elyot Grant

    Timothy M. Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and covering problems.Computational Geometry Theory and Applications, 47(2):112– 124, 2014

    work page 2014

  12. [12]

    Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe

    Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. InProceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1576– 1585, 2012

    work page 2012

  13. [13]

    Chan and Sariel Har-Peled

    Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks.Discrete and Computational Geometry, 48(2):373–392, 2012

    work page 2012

  14. [14]

    Parameterized approximation for maximum weight independent set of rectangles and segments

    Jana Cslovjecsek, Michal Pilipczuk, and Karol Węgrzycki. Parameterized approximation for maximum weight independent set of rectangles and segments. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, LIPIcs, page...

    work page 2024

  15. [15]

    Approximation ofk-set cover by semi-local optimization

    Rong-chii Duh and Martin Fürer. Approximation ofk-set cover by semi-local optimization. In Frank Thomson Leighton and Peter W. Shor, editors,Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 256–264. ACM, 1997

    work page 1997

  16. [16]

    Hitting sets when the vc-dimension is small.Inf

    Guy Even, Dror Rawitz, and Shimon Shahar. Hitting sets when the vc-dimension is small.Inf. Process. Lett., 95(2):358–362, 2005

    work page 2005

  17. [17]

    Fekete, Kan Huang, Joseph S

    Sándor P. Fekete, Kan Huang, Joseph S. Mitchell, Ojas Parekh, and Cynthia A. Phillips. Geometric hitting set for segments of few orientations.Theor. Comp. Sys., 62(2):268–303, February 2018

    work page 2018

  18. [18]

    Applications of a new separator theorem for string graphs.Comb

    Jacob Fox and János Pach. Applications of a new separator theorem for string graphs.Comb. Probab. Comput., 23(1):66–74, 2014

    work page 2014

  19. [19]

    Approximation algorithms for polynomial-expansion and low-density graphs

    Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. InAlgorithms – ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings, pages 717–728, 2015

    work page 2015

  20. [20]

    epsilon-nets and simplex range queries.Discrete & Computa- tional Geometry, 2:127–151, 1987

    David Haussler and Emo Welzl. epsilon-nets and simplex range queries.Discrete & Computa- tional Geometry, 2:127–151, 1987. 18

    work page 1987

  21. [21]

    Clique is hard to approximate withinn1−ε.Acta Mathematica, 182(1):105–142, 1999

    J Håstad. Clique is hard to approximate withinn1−ε.Acta Mathematica, 182(1):105–142, 1999

    work page 1999

  22. [22]

    Parameterized and approximation algorithms for coverings points with segments in the plane

    Katarzyna Kowalska and Michał Pilipczuk. Parameterized and approximation algorithms for coverings points with segments in the plane. In41st International Symposium on Theoretical Aspects of Computer Science, 2024

    work page 2024

  23. [23]

    Lipton and Robert E

    Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979

    work page 1979

  24. [24]

    Parameterized complexity of independence and domination on geometric graphs

    Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), volume 4169 ofLecture Notes in Computer Science, pages 154–165. Springer, 2006

    work page 2006

  25. [25]

    How to net a lot with little: Small epsilon-nets for disks and halfspaces

    Jirí Matousek, Raimund Seidel, and Emo Welzl. How to net a lot with little: Small epsilon-nets for disks and halfspaces. In Raimund Seidel, editor,Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990, pages 16–22. ACM, 1990

    work page 1990

  26. [26]

    Mustafa.Sampling in combinatorial and geometric set systems, volume 265

    Nabil H. Mustafa.Sampling in combinatorial and geometric set systems, volume 265. American Mathematical Society, 2022

    work page 2022

  27. [27]

    Mustafa, Rajiv Raman, and Saurabh Ray

    Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces.SIAM Journal on Computing, 44(6):1650–1669, 2015

    work page 2015

  28. [28]

    Mustafa and Saurabh Ray

    Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883–895, 2010

    work page 2010

  29. [29]

    Tight lower bounds for the size of epsilon-nets

    János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. InProceedings of the twenty-seventh annual symposium on Computational geometry, pages 458–463, 2011

    work page 2011

  30. [30]

    Graphs drawn with few crossings per edge.Comb., 17(3):427–439, 1997

    János Pach and Géza Tóth. Graphs drawn with few crossings per edge.Comb., 17(3):427–439, 1997

    work page 1997

  31. [31]

    New existence proofs forϵ-nets

    Evangelia Pyrga and Saurabh Ray. New existence proofs forϵ-nets. InProceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SoCG ’08, pages 199–207, New York, NY, USA, 2008. ACM

    work page 2008

  32. [32]

    Constructing planar support for non-piercing regions.Discrete and Computational Geometry, 64(3):1098–1122, 2020

    Rajiv Raman and Saurabh Ray. Constructing planar support for non-piercing regions.Discrete and Computational Geometry, 64(3):1098–1122, 2020

    work page 2020

  33. [33]

    John Wiley & Sons, 1998

    Alexander Schrijver.Theory of linear and integer programming. John Wiley & Sons, 1998

    work page 1998

  34. [34]

    Weighted geometric set cover via quasi-uniform sampling

    Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. InProceedings of the 42nd ACM Symposium on Theory of Computing, pages 641–648, 2010. 19 A Deferred Proof for Stochastic Dominance Lemma 2.5.Let X1,X 2,Y 1,Y 2 be random variables such thatX1 is independent ofX2 and Y1 is independent ofY 2. IfX 1⪯stY1 andX 2⪯stY2, thenX 1 +X 2⪯st...

    work page 2010