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

(28)

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

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)