Tighter estimates for \(\epsilon\)-nets for disks
type: Item
instance of: scholarly article
title: Tighter estimates for \(\epsilon\)-nets for disks
zbMATH Open document ID: 1334.65048
author: Norbert Bus
author: Shashwat Garg
author: Nabil H. Mustafa
author: Saurabh Ray
published in: Computational Geometry
publication date: 2016-04-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/1501.03246
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6567427
zbMATH Keywords: epsilon nets
zbMATH Keywords: Delaunay triangulations
zbMATH Keywords: disks
zbMATH Keywords: hitting sets
MaRDI profile type: Publication
OpenAlex ID: W2202493075
arXiv ID: 1501.03246
cites work: Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
cites work: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
cites work: Small strong epsilon nets
cites work: Almost optimal set covers in finite VC-dimension
cites work: Q2954994
cites work: Geometric Hitting Sets for Disks: Theory and Practice
cites work: Covering Points by Unit Disks of Fixed Location
cites work: Q5743501
cites work: A deterministic view of random sampling and its use in geometry
cites work: Improved approximation algorithms for geometric set cover
cites work: AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
cites work: ON THE DISCRETE UNIT DISK COVER PROBLEM
cites work: Hitting sets when the VC-dimension is small
cites work: Q4198056
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Fast approximation algorithms for a nonconvex covering problem
cites work: Reducibility among Combinatorial Problems
cites work: Almost tight bounds for \(\epsilon\)-nets
cites work: Efficient partition trees
cites work: On constants for cuttings in the plane
cites work: Q4530626
cites work: Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
cites work: Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension
cites work: Improved results on geometric hitting set problems
cites work: Q2965518
cites work: New existence proofs ε-nets
cites work: Q4527015
cites work: Epsilon nets and union complexity
cites work: Weighted geometric set cover via quasi-uniform sampling
DOI: 10.1016/J.COMGEO.2015.12.002
description: scientific article; zbMATH DE number 6567427