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 algorithmsset coverhitting setmultiplicative weight methodgeometric range space

Mathematics Subject Classification ID

Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) 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

(29)

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

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)