Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

DOI10.1145/2582112.2582152MaRDI QIDQ4635551zbMATH OpenOpenAlexFDO

Authors Jiangwei Pan, Pankaj K. Agarwal

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2582112.2582152

zbMATH Keywords

approximation algorithmsgeometric range spacehitting setmultiplicative weight methodset cover

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Near-linear algorithms for geometric hitting sets and set covers
• Near-linear approximation algorithms for geometric hitting sets
• Near-linear approximation algorithms for geometric hitting sets
• Practical and efficient algorithms for the geometric hitting set problem
• Approximation algorithms for a geometric set cover problem
• Faster approximation algorithms for geometric set cover
• An exact algorithm for a class of geometric set-cover problems
• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Exact and approximation algorithms for geometric and capacitated set cover problems

Cited in

(30)

• Approximability and hardness of geometric hitting set with axis-parallel rectangles
• Practical and efficient algorithms for the geometric hitting set problem
• \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity
• On separating points by lines
• Experiments with unit disk cover algorithms for covering massive pointsets
• The maximum exposure problem
• Near-linear algorithms for geometric hitting sets and set covers
• Near-linear approximation algorithms for geometric hitting sets
• Tighter estimates for -nets for disks
• Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Geometric hitting sets for disks: theory and practice
• Finding small hitting sets in infinite range spaces of bounded VC-dimension
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• On Geometric Set Cover for Orthants
• Computing optimal \(\varepsilon\)-nets is as easy as finding an unhit set
• Limits of local search: quality and efficiency
• Improved approximation algorithms for geometric set cover
• Near-linear approximation algorithms for geometric hitting sets
• Clustering geometrically-modeled points in the aggregated uncertainty model
• The Maximum Exposure Problem.
• Computing coverage kernels under restricted settings
• Improved results on geometric hitting set problems
• Faster approximation algorithms for geometric set cover
• Improved algorithms for minimum-membership geometric set cover
• PTAS for minimum cost multicovering with disks
• Online and dynamic algorithms for geometric set cover and hitting set
• Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications
• Approximating densest subgraph in geometric intersection graphs
• Improved approximation algorithms for geometric set cover

This page was built for publication: Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635551)