Small strong epsilon nets
type: Item
instance of: scholarly article
title: Small strong epsilon nets
zbMATH Open document ID: 1307.65025
author: Pradeesha Ashok
author: Umair Azmi
author: Sathish Govindarajan
published in: Computational Geometry
publication date: 2014-08-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1208.2785
review text: This paper continues weak \(\epsilon\)-nets problem for convex objects, disks, axis-parallel rectangles and halfspaces, where the size of the weak \(\epsilon\)-net is fixed as a small integer \(i\), and the value of \(\epsilon_i\) is bounded. Here, the study of small strong \(\epsilon\)-nets for a family of axis-parallel rectangles, halfspaces and disks is initiated. Let \(S\) be a family of geometric objects, and \(\epsilon_i^S\in[0,1]\) represents the smallest real number such that for any given point set \(P\) there exists \(Q\subset P\) of size \(i\) which is an \(\epsilon_i^S\)-net with respect to the family \(S\). Bounds of \(\epsilon_i^S\) for small values of \(i\) are investigated and upper and lower bounds of \(\epsilon_i^S\) are given for the family of axis-parallel rectangles, halfspaces and disks. The obtained results can be used in many applications such as statistics, combinatorial geometry, geometric algorithms, mesh partitioning, etc.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6329751
zbMATH Keywords: epsilon nets
zbMATH Keywords: cetrepoint
zbMATH Keywords: strong centrepoint
zbMATH Keywords: \(\epsilon\)-nets
zbMATH Keywords: weak \(\epsilon\)-nets
zbMATH Keywords: small weak \(\epsilon\)-nets
zbMATH Keywords: strong \(\epsilon\)-nets
zbMATH Keywords: small strong \(\epsilon\)-nets
zbMATH Keywords: axis-parallel rectangle
zbMATH Keywords: halfspace
zbMATH Keywords: disk
zbMATH Keywords: combinatorial geometry
zbMATH Keywords: geometric algorithms
zbMATH Keywords: mesh partitioning
MaRDI profile type: Publication
OpenAlex ID: W2121777229
arXiv ID: 1208.2785
cites work: A non-linear lower bound for planar epsilon-nets
cites work: Small weak epsilon-nets
cites work: Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
cites work: Lower bounds for weak epsilon-nets and stair-convexity
cites work: Improved bounds on weak \(\varepsilon\)-nets for convex sets
cites work: APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
cites work: Improved approximation algorithms for geometric set cover
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Computing a centerpoint of a finite planar set of points in linear time
cites work: Almost tight bounds for \(\epsilon\)-nets
cites work: New constructions of weak \(\varepsilon\)-nets
cites work: Approximate centerpoints with proofs
cites work: Separators for sphere-packings and nearest neighbor graphs
cites work: Q4288580
cites work: Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension
cites work: An optimal extension of the centerpoint theorem
cites work: Tight lower bounds for the size of epsilon-nets
cites work: New existence proofs ε-nets
cites work: A Theorem on General Measure
cites work: Polychromatic coloring for half-planes
cites work: Epsilon nets and union complexity
DOI: 10.1016/J.COMGEO.2014.05.002
description: scientific article; zbMATH DE number 6329751