Name
Abstract | ||
|---|---|---|
Let P be a set of n points in 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 dnd+1 points of P. We call a point x a strong centerpoint for a family of objects C if [email protected]?P is contained in every object [email protected]?C that contains more than a constant fraction of points of P. A strong centerpoint does not exist even for halfspaces in R^2. We prove that a strong centerpoint exists for axis-parallel boxes in R^d and give exact bounds. We then extend this to small strong @e-nets in the plane. Let @e"i^S represent the smallest real number in [0,1] such that there exists an @e"i^S-net of size i with respect to S. We prove upper and lower bounds for @e"i^S where S is the family of axis-parallel rectangles, halfspaces and disks. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.comgeo.2014.05.002 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
ε-nets,axis-parallel rectangles,centerpoint,small weak ε-nets | Conference | 47 |
Issue | ISSN | Citations |
9 | 0925-7721 | 5 |
PageRank | References | Authors |
0.46 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pradeesha Ashok | 1 | 11 | 6.11 |
| Umair Azmi | 2 | 5 | 0.46 |
| Sathish Govindarajan | 3 | 110 | 12.84 |