Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

DOI10.1145/2582112.2582152zbMath1398.68656OpenAlexW1977333786MaRDI QIDQ4635551

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

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

Related Items (15)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ The maximum exposure problem ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Geometric Hitting Sets for Disks: Theory and Practice ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity ⋮ The Maximum Exposure Problem. ⋮ On separating points by lines ⋮ Limits of local search: quality and efficiency ⋮ Unnamed Item ⋮ Computing coverage kernels under restricted settings ⋮ On Geometric Set Cover for Orthants ⋮ Experiments with unit disk cover algorithms for covering massive pointsets ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

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