Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
From MaRDI portal
Recommendations
- Near-linear approximation algorithms for geometric hitting sets
- Near-linear approximation algorithms for geometric hitting sets
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Independent and hitting sets of rectangles intersecting a diagonal line
- On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation schemes for covering and packing problems in image processing and VLSI
- Computational geometry. Algorithms and applications.
- Covering and coloring problems for relatives of intervals
- Covering boxes by points
- Fast stabbing of boxes in high dimensions
- Improved results on geometric hitting set problems
- Independent set of intersection graphs of convex objects in 2D
- Intersection Graphs of Rectangles and Segments
- Jump number of two-directional orthogonal ray graphs
- Maximum independent set of rectangles
- On point covers of parallel rectangles
- Optimal packing and covering in the plane are NP-complete
- Polynomial-time approximation schemes for packing and piercing fat objects
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
Cited in
(14)- A lower bound for the hitting set size for combinatorial rectangles and an application
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
- On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
- Grid intersection graphs and order dimension
- Covering, hitting, piercing and packing rectangles intersecting an inclined line
- Dominating set of rectangles intersecting a straight line
- On dominating set of some subclasses of string graphs
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- Hitting and Piercing Rectangles Induced by a Point Set
- Packing and covering with balls on Busemann surfaces
- Covering and packing of triangles intersecting a straight line
- Max point-tolerance graphs
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
This page was built for publication: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q364848)
