Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
From MaRDI portal
Publication:3467840
DOI10.1007/978-3-319-26626-8_10zbMath1478.90112OpenAlexW2296147893MaRDI QIDQ3467840
Apurva Mudgal, Supantha Pandit
Publication date: 5 February 2016
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_10
coveringpackingNP-completenesssquaresexact algorithmrectangleshittingpiercinginclined linediagonal lineunit-height
Related Items (8)
Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ On dominating set of some subclasses of string graphs ⋮ ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Dominating set of rectangles intersecting a straight line ⋮ Covering and packing of triangles intersecting a straight line ⋮ Covering and packing of rectilinear subdivision ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
Cites Work
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Approximation algorithms for maximum independent set of a unit disk graph
- A weighted min-max relation for intervals
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- PTAS for Weighted Set Cover on Unit Squares
- Planar Formulae and Their Uses
- The Problem of Compatible Representatives
- The Rectilinear Steiner Tree Problem is $NP$-Complete
This page was built for publication: Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
