Computing optimal -nets is as easy as finding an unhit set

DOI10.4230/LIPICS.ICALP.2019.87MaRDI QIDQ5091247zbMATH OpenFDO

Authors Nabil H. Mustafa

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2019.87

zbMATH Keywords

\(\varepsilon\)-netsgeometric set systems

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• A simple proof of optimal epsilon nets
• Tighter estimates for -nets for disks
• New Lower Bounds for ϵ-nets
• Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
• The \(\varepsilon\)-\(t\)-net problem

Cites work

• -nets and simplex range queries
• A Randomized Algorithm for Closest-Point Queries
• A simple proof of optimal epsilon nets
• A simple proof of the shallow packing lemma
• Almost tight bounds for -nets
• Applications of random sampling in computational geometry. II
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Practical low-dimensional halfspace range space sampling
• Practical methods for shape fitting and kinetic data structures using coresets
• Reporting points in halfspaces
• Small-size -nets for axis-parallel rectangles and boxes
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tighter estimates for -nets for disks
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(3)

• A simple proof of optimal epsilon nets
• Hitting sets when the shallow cell complexity is small
• Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications

This page was built for publication: Computing optimal \(\varepsilon\)-nets is as easy as finding an unhit set

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