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

combinatorial geometryepsilon netshalfspacedisk\(\epsilon\)-netsaxis-parallel rectanglecetrepointgeometric algorithmsmesh 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$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 554764 (Why is no real title available?)
• A Theorem on General Measure
• A non-linear lower bound for planar epsilon-nets
• APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
• Almost tight bounds for -nets
• An optimal extension of the centerpoint theorem
• Approximate centerpoints with proofs
• Computing a centerpoint of a finite planar set of points in linear time
• Epsilon nets and union complexity
• 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 \(\varepsilon\)-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
• -nets and simplex range queries

Cited in

(4)

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

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)