Hitting Axis-Parallel Segments with Weighted Points
Rajiv Raman, Siddhartha Sarkar, Jatin Yadav · 2026
Read Hitting Axis-Parallel Segments with Weighted Points by Rajiv Raman, Siddhartha Sarkar, Jatin Yadav (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14499.txt.
Introduction
Raman, Sarkar and Yadav tackle choosing the cheapest weighted points that touch every horizontal and vertical segment in a plane. Splitting the problem by direction gives only a factor-two guarantee, so they round a linear program on horizontal lines and repair the leftover vertical parts exactly. Their claimed guarantees beat factor two in both weighted and unweighted cases, and they extend the method to more orientations.
Catalog record
| CREATOR | Rajiv Raman, Siddhartha Sarkar, Jatin Yadav |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65940 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14499
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hitting Axis-Parallel Segments with Weighted Points Rajiv Raman, Siddhartha Sarkar, Jatin Yadav Abstract We study a geometric hitting-set problem in which the input consists of a set P P of weighted points and a family 𝒮 = ℋ ∪ 𝒱 \mathcal{S}=\mathcal{H}\cup\mathcal{V} of axis-parallel segments in the plane. The goal is to select a minimum-weight subset of P P that hits every segment in 𝒮 \mathcal{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 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 ) (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 ) ) (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 1+1/e and show that the problem is APX-hard. We also present algorithms for the generalization to d d orientations, as well as PTASes for bounded-complexity subclasses of the unweighted Hitting Set problem. 1 Introduction A set system (P,\mathcal{S}) consists of a set P of elements and a collection \mathcal{S} of subsets of P . Given a set system, (P,\mathcal{S}) , a set P^{\prime}\subseteq P is a hitting set if each set in \mathcal{S} contains an element of P^{\prime} . In the unweighted Hitting Set Problem, the goal is to find a hitting set of minimum cardinality, and in the weighted Hitting Set Problem, we are additionally given a weight function w:P\to\mathbb{R} and the goal is to select a minimum weight hitting set P^{\prime} , i.e., a hitting set such that \sum_{p\in P^{\prime}}w(p) is minimized. The set systems considered in this paper are finite. We assume that |P|=n and |\mathcal{S}|=m . Without restrictions, the Hitting Set Problem is equivalent to the Set Cover Problem on the dual set system , where points in P and sets in \mathcal{S} swap roles. For these general systems, O(\log m) -approximation algorithms exist with nearly matching lower bounds. However, we can often bypass these limits by exploiting the structure of restricted instances. This paper focuses on geometric set systems , where elements and sets are defined by objects in the plane. While Hitting Set and Set Cover remain NP-hard in these settings, they frequently admit better approximation ratios than general systems. Despite this, a unified set of techniques and a complete characterization of these systems remain elusive. There are two broad frameworks that yield improved approximation algorithms for Hitting Set and Set Cover. The first is via \epsilon -nets and LP-rounding ( [ 21 , 8 , 16 , 34 , 11 ] ) that yield algorithms with approximation factors depending on the combinatorial complexity (such as VC-dimension , or shallow-cell complexity ) of the instance. However, these techniques at best yield O(1) -approximation algorithms with large hidden constants even for simple objects such disks or squares. A second framework is local search , that yields PTASes when the geometric set system is non-piercing , but works only in the unweighted setting [ 27 , 13 , 32 ] . Informally, a set \mathcal{S} of objects in the plane is non-piercing if the boundary of each object in \mathcal{S} is a simple Jordan curve, and for any A,B\in\mathcal{S} , A\setminus B and B\setminus A are both connected sets (see [ 32 ] for a precise definition). On the other hand, Chan and Grant [ 11 ] (see also Har-Peled and Quanrud [ 19 ] ) showed even with nearly congruent almost-squares , the Set Cover and Hitting Set problems become APX-hard. Recently, Banik et al. [ 6 ] showed that the local search technique yields a PTAS for the Set Cover problem even when the geometric shapes are not non-piercing, i.e., they pierce , but in a bounded manner. However, no such result is known for the Hitting Set Problem. Our goal is to develop improved approximation algorithms for structured, weighted geometric set systems. Specifically, we address the Hitting Set problem for axis-parallel line segments (formally defined below). Weighted Geometric Hitting Set for Axis-Parallel Segments Input: A finite set P of points in the plane with a non-negative weight function w\colon P\to\mathbb{R}_{\geq 0} , and a family \mathcal{S}=\mathcal{H}\cup\mathcal{V} of axis-parallel segments (where \mathcal{H} are horizontal and \mathcal{V} are vertical). Goal: Find a subset Q\subseteq P that minimizes the total weight \sum_{p\in Q}w(p) such that Q hits every segment in \mathcal{S} (i.e., Q\cap s\neq\emptyset for all s\in\mathcal{S} ). Axis-parallel segments generalize several tractable special cases. When all segments in \mathcal{S} are parallel to a single axis, the problem becomes one-dimensional; alternatively, if segments only intersect those of orthogonal orientations, the problem maps to bipartite graphs. In both scenarios, the Hitting Set, Set Cover, and also the Independent Set problems are solvable in polynomial time because their natural LP-relaxations are integral, owing to totally unimodular constraint matrices [ 33 ] . Crucially, this total unimodularity breaks down in our setting, where segments possess both orientations and parallel segments overlap. For Hitting Set, Set Cover, and Independent Set, a trivial 2-approximation follows from independently solving the one-dimensional sub-instances for each axis and combining the results. Remarkably, while this remains the best-known approximation factor for Set Cover and Independent Set, our primary contribution is breaking this factor-2 barrier for the weighted Hitting Set problem. 1.1 Our Contributions Our main contribution is a suite of improved approximation algorithms for the Hitting Set problem on axis-parallel line segments and points in the plane, summarized in Table 1 . For line segments in two orientations, we achieve a (1+2/e)\approx 1.74 -approximation in the weighted setting and a (1+1/(e-1))\approx 1.58 -approximation in the unweighted setting. When one orientation consists of infinite lines instead of segments, we improve this to a (1+1/e)\approx 1.36 -approximation. We further generalize our results to segments parallel to one of d directions. These results are obtained via a randomized rounding procedure on the natural linear program, but can be derandomized using the standard method of conditional expectations. For the sake of completeness, we include the derandomization in Appendix C . We also present a PTAS for specific restricted instances. Problem Approx. Factor Complexity Previous bounds Wt. axis-parallel 1+2/e (Th. 1.1 ) 2 Unwt. axis-parallel 1+1/(e-1) (Th. 1.2 ) 2 , APX-hard [ 17 ] d -dir wt. \ln d+\ln\ln d+O(1) (Th. 1.3 ) d Hor-seg, vert lines 1+1/e (Thm. 1.5 ) APX-hard (Thm. 1.6 ) 5/3 [ 17 ] k -restricted unwt. PTAS (Thm. 1.8 ) NP-hard Lines in 3-directions APX-hard (Thm. 1.7 ) 4/3 [ 15 ] , NP-hard [ 17 ] Table 1: The table above summarizes our results. Note that the previously best-known 2-approximation is considered a folklore result. Theorem 1.1 (Weighted) . Let \mathcal{S}=\mathcal{H}\cup\mathcal{V} be a set