Small strong epsilon nets

DOI10.1016/J.COMGEO.2014.05.002MaRDI QIDQ396471zbMATH OpenOpenAlexFDO

Authors Pradeesha Ashok, Umair Azmi, Sathish Govindarajan

Publication date 13 August 2014

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

\(\epsilon\)-netsaxis-parallel rectanglecetrepointcombinatorial geometrydiskepsilon netsgeometric algorithmshalfspacemesh partitioningsmall strong \(\epsilon\)-netssmall weak \(\epsilon\)-netsstrong \(\epsilon\)-netsstrong centrepointweak \(\epsilon\)-nets

Mathematics Subject Classification ID

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

Abstract: Let P be a set of n points in $mathbb{R}^d$. A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than $dnoverd+1$ points of P. We call a point x a strong centerpoint for a family of objects $mathcalC$ if $xinP$ is contained in every object $CinmathcalC$ that contains more than a constant fraction of points of P. A strong centerpoint does not exist even for halfspaces in $mathbb{R}^2$. We prove that a strong centerpoint exists for axis-parallel boxes in $mathbb{R}^d$ and give exact bounds. We then extend this to small strong $epsilon$-nets in the plane and prove upper and lower bounds for $epsilo{n}_i^{m}athcalS$ where $mathcalS$ is the family of axis-parallel rectangles, halfspaces and disks. Here $epsilo{n}_i^{m}athcalS$ represents the smallest real number in $[0,1]$ such that there exists an $epsilo{n}_i^{m}athcalS$-net of size i with respect to $mathcalS$.

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.

Recommendations

• Small weak epsilon-nets
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• New constructions of weak epsilon-nets
• Small-size -nets for axis-parallel rectangles and boxes
• Small-size ε-nets for axis-parallel rectangles and boxes

Cites work

• -nets and simplex range queries
• A non-linear lower bound for planar epsilon-nets
• A Theorem on General Measure
• Almost tight bounds for -nets
• An optimal extension of the centerpoint theorem
• Approximate centerpoints with proofs
• APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
• Computing a centerpoint of a finite planar set of points in linear time
• Epsilon nets and union complexity
• scientific article; zbMATH DE number 554764 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• New constructions of weak -nets
• New existence proofs ε-nets
• Polychromatic coloring for half-planes
• Separators for sphere-packings and nearest neighbor graphs
• Small weak epsilon-nets
• Small-size -nets for axis-parallel rectangles and boxes
• Tight lower bounds for the size of epsilon-nets
• Weak -nets have basis of size O(1/ (1/)) in any dimension

Cited in

(4)

• Small weak epsilon-nets
• Tighter estimates for -nets for disks
• Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
• On strong centerpoints

This page was built for publication: Small strong epsilon nets

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