Small strong epsilon nets (Q396471): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / 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. | |||
Property / 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ivana Linkeová / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65D18 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6329751 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
epsilon nets | |||
Property / zbMATH Keywords: epsilon nets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
cetrepoint | |||
Property / zbMATH Keywords: cetrepoint / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
strong centrepoint | |||
Property / zbMATH Keywords: strong centrepoint / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
\(\epsilon\)-nets | |||
Property / zbMATH Keywords: \(\epsilon\)-nets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
weak \(\epsilon\)-nets | |||
Property / zbMATH Keywords: weak \(\epsilon\)-nets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
small weak \(\epsilon\)-nets | |||
Property / zbMATH Keywords: small weak \(\epsilon\)-nets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
strong \(\epsilon\)-nets | |||
Property / zbMATH Keywords: strong \(\epsilon\)-nets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
small strong \(\epsilon\)-nets | |||
Property / zbMATH Keywords: small strong \(\epsilon\)-nets / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
axis-parallel rectangle | |||
Property / zbMATH Keywords: axis-parallel rectangle / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
halfspace | |||
Property / zbMATH Keywords: halfspace / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
disk | |||
Property / zbMATH Keywords: disk / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
combinatorial geometry | |||
Property / zbMATH Keywords: combinatorial geometry / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
geometric algorithms | |||
Property / zbMATH Keywords: geometric algorithms / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
mesh partitioning | |||
Property / zbMATH Keywords: mesh partitioning / rank | |||
Normal rank |
Revision as of 16:24, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Small strong epsilon nets |
scientific article |
Statements
Small strong epsilon nets (English)
0 references
13 August 2014
0 references
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.
0 references
epsilon nets
0 references
cetrepoint
0 references
strong centrepoint
0 references
\(\epsilon\)-nets
0 references
weak \(\epsilon\)-nets
0 references
small weak \(\epsilon\)-nets
0 references
strong \(\epsilon\)-nets
0 references
small strong \(\epsilon\)-nets
0 references
axis-parallel rectangle
0 references
halfspace
0 references
disk
0 references
combinatorial geometry
0 references
geometric algorithms
0 references
mesh partitioning
0 references