Near-linear approximation algorithms for geometric hitting sets
From MaRDI portal
Publication:2429345
DOI10.1007/s00453-011-9517-2zbMath1286.68493OpenAlexW1964481538MaRDI QIDQ2429345
Esther Ezra, Pankaj K. Agarwal, Micha Sharir
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9517-2
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (6)
Covering problem on fuzzy graphs and its application in disaster management system ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Union of random Minkowski sums and network vulnerability analysis ⋮ On separating points by lines ⋮ Limits of local search: quality and efficiency ⋮ Near-linear algorithms for geometric hitting sets and set covers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation for guarding simple galleries from the perimeter
- Improved approximation algorithms for geometric set cover
- Dynamic fractional cascading
- Hitting sets when the VC-dimension is small
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- \(\epsilon\)-nets and simplex range queries
- Optimal packing and covering in the plane are NP-complete
- Reporting points in halfspaces
- On arrangements of Jordan arcs with three intersections per pair
- Fast stabbing of boxes in high dimensions
- Applications of random sampling in computational geometry. II
- Almost optimal set covers in finite VC-dimension
- On the Boundary Complexity of the Union of Fat Triangles
- A threshold of ln n for approximating set cover
- Generalized Selection and Ranking: Sorted Matrices
- New existence proofs ε-nets
- On Approximating the Depth and Related Problems
- Efficient Colored Orthogonal Range Counting
- Approximation schemes for covering and packing problems in image processing and VLSI
- Computing Many Faces in Arrangements of Lines and Segments
- Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Polynomial-time approximation schemes for packing and piercing fat objects
- Geometric Set Cover and Hitting Sets for Polytopes in R
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- Epsilon nets and union complexity
- PTAS for geometric hitting set problems via local search
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Tight lower bounds for the size of epsilon-nets
- Orthogonal range reporting
- Improved Bounds for the Union of Locally Fat Objects in the Plane
This page was built for publication: Near-linear approximation algorithms for geometric hitting sets
