Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve

DOI10.1016/j.comgeo.2013.05.008zbMath1270.05028OpenAlexW2030479143MaRDI QIDQ364848

Stefan Felsner, Victor Chepoi

Publication date: 3 September 2013

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S092577211300059X

zbMATH Keywords

approximation algorithmtransversalsaxis-monotone curvefactor 6 algorithmminimum hitting setaxis-parallel rectanglespacking and covering

Mathematics Subject Classification ID

Transversal (matching) theory (05D15) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Related Items (11)

Packing and covering with balls on Busemann surfaces ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ On dominating set of some subclasses of string graphs ⋮ Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line ⋮ Max point-tolerance graphs ⋮ ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE ⋮ Dominating set of rectangles intersecting a straight line ⋮ Grid intersection graphs and order dimension ⋮ Covering and packing of triangles intersecting a straight line ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved results on geometric hitting set problems
• Covering boxes by points
• Covering and coloring problems for relatives of intervals
• Optimal packing and covering in the plane are NP-complete
• On point covers of parallel rectangles
• Fast stabbing of boxes in high dimensions
• Almost optimal set covers in finite VC-dimension
• Independent set of intersection graphs of convex objects in 2D
• Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
• Jump Number of Two-Directional Orthogonal Ray Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation algorithms for maximum independent set of pseudo-disks
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• Intersection Graphs of Rectangles and Segments

This page was built for publication: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve