2026-09-10T09:44:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27731 2026-09-09T12:19:35Z ddc:004 open_access

Hitting Axis-Parallel Segments with Weighted Points Raman, Rajiv Sarkar, Siddhartha Yadav, Jatin Geometric Hitting Set Approximation Algorithms Computational Geometry LP Rounding Axis-Parallel Segments PTAS APX-hardness We study a geometric hitting-set problem in which the input consists of a set P of weighted points and a family 𝒮 = ℋ∪𝒱 of axis-parallel segments in the plane. The goal is to select a minimum-weight subset of P that hits every segment in 𝒮. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajiv Raman and Siddhartha Sarkar and Jatin Yadav 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.14 urn:nbn:de:0030-drops-277313 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.14 eng https://creativecommons.org/licenses/by/4.0/legalcode