Tighter estimates for \(\epsilon\)-nets for disks

DOI10.1016/j.comgeo.2015.12.002zbMath1334.65048arXiv1501.03246OpenAlexW2202493075MaRDI QIDQ265723

Norbert Bus, Saurabh Ray, Shashwat Garg, Nabil H. Mustafa

Publication date: 12 April 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.03246

zbMATH Keywords

Delaunay triangulationsdisksepsilon netshitting sets

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (8)

A PTAS for the Weighted Unit Disk Cover Problem ⋮ On the geometric set multicover problem ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ Limits of local search: quality and efficiency ⋮ Unnamed Item ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small strong epsilon nets
• Improved results on geometric hitting set problems
• A deterministic view of random sampling and its use in geometry
• Hitting sets when the VC-dimension is small
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Efficient partition trees
• On constants for cuttings in the plane
• Almost optimal set covers in finite VC-dimension
• Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension
• Weighted geometric set cover via quasi-uniform sampling
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Geometric Hitting Sets for Disks: Theory and Practice
• AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• New existence proofs ε-nets
• Fast approximation algorithms for a nonconvex covering problem
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Reducibility among Combinatorial Problems
• ON THE DISCRETE UNIT DISK COVER PROBLEM
• Improved approximation algorithms for geometric set cover
• Epsilon nets and union complexity
• Covering Points by Unit Disks of Fixed Location

This page was built for publication: Tighter estimates for \(\epsilon\)-nets for disks