Small strong epsilon nets (Q396471): Difference between revisions

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.