DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.14

Hitting Axis-Parallel Segments with Weighted Points

Authors: Rajiv Raman, Siddhartha Sarkar, and Jatin Yadav

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Rajiv Raman, Siddhartha Sarkar, and Jatin Yadav. Hitting Axis-Parallel Segments with Weighted Points. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{raman_et_al:LIPIcs.APPROX/RANDOM.2026.14,
  author =	{Raman, Rajiv and Sarkar, Siddhartha and Yadav, Jatin},
  title =	{{Hitting Axis-Parallel Segments with Weighted Points}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.14},
  URN =		{urn:nbn:de:0030-drops-277313},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.14},
  annote =	{Keywords: Geometric Hitting Set, Approximation Algorithms, Computational Geometry, LP Rounding, Axis-Parallel Segments, PTAS, APX-hardness}
}

Search Results

Documents authored by Sarkar, Siddhartha

Hitting Axis-Parallel Segments with Weighted Points

Abstract

Cite as

Thanks for your feedback!

Could not send message