Near-linear approximation algorithms for geometric hitting sets

DOI10.1007/s00453-011-9517-2zbMath1286.68493MaRDI 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

zbMATH Keywords

approximation algorithms; hitting sets; cuttings; geometric range spaces

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Related Items

Constant-Factor Approximation for TSP with Disks, Union of random Minkowski sums and network vulnerability analysis, Limits of local search: quality and efficiency, On separating points by lines, Covering problem on fuzzy graphs and its application in disaster management system, 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