Near-linear approximation algorithms for geometric hitting sets
From MaRDI portal
Recommendations
- Near-linear approximation algorithms for geometric hitting sets
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- Near-linear algorithms for geometric hitting sets and set covers
- Practical and efficient algorithms for the geometric hitting set problem
- Geometric hitting sets for disks: theory and practice
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- scientific article; zbMATH DE number 1424290 (Why is no real title available?)
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- A threshold of ln n for approximating set cover
- Almost optimal set covers in finite VC-dimension
- Applications of random sampling in computational geometry. II
- Approximation schemes for covering and packing problems in image processing and VLSI
- Computational geometry. Algorithms and applications.
- Computing Many Faces in Arrangements of Lines and Segments
- Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
- Dynamic fractional cascading
- Efficient Colored Orthogonal Range Counting
- Epsilon nets and union complexity
- Fast stabbing of boxes in high dimensions
- Generalized Selection and Ranking: Sorted Matrices
- Geometric Set Cover and Hitting Sets for Polytopes in R
- Hitting sets when the VC-dimension is small
- Improved approximation algorithms for geometric set cover
- Improved approximation for guarding simple galleries from the perimeter
- Improved bound for the union of fat triangles
- Improved bounds for the union of locally fat objects in the plane
- New existence proofs ε-nets
- On Approximating the Depth and Related Problems
- On arrangements of Jordan arcs with three intersections per pair
- On the Boundary Complexity of the Union of Fat Triangles
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Optimal packing and covering in the plane are NP-complete
- Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
- PTAS for geometric hitting set problems via local search
- Polynomial-time approximation schemes for packing and piercing fat objects
- Reporting points in halfspaces
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- State of the union (of geometric objects)
- Tight lower bounds for the size of epsilon-nets
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- \(\epsilon\)-nets and simplex range queries
Cited in
(21)- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- On the minimum hitting set of bundles problem
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
- Covering problem on fuzzy graphs and its application in disaster management system
- Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- Near-linear algorithms for geometric hitting sets and set covers
- On separating points by lines
- Improved results on geometric hitting set problems
- PTAS for geometric hitting set problems via local search
- Approximability and hardness of geometric hitting set with axis-parallel rectangles
- Finding small hitting sets in infinite range spaces of bounded VC-dimension
- On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
- Constant-factor approximation for TSP with disks
- Near-linear approximation algorithms for geometric hitting sets
- Practical and efficient algorithms for the geometric hitting set problem
- scientific article; zbMATH DE number 5019895 (Why is no real title available?)
- Limits of local search: quality and efficiency
- Minimum membership hitting sets of axis parallel segments
- Union of random Minkowski sums and network vulnerability analysis
- Tighter estimates for \(\epsilon\)-nets for disks
This page was built for publication: Near-linear approximation algorithms for geometric hitting sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429345)
