Loading...
Please wait, while we are loading the content...
Similar Documents
Near-Optimal Lower Bounds for Epsilon-nets for Half-spaces and Low Complexity Set Systems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kupavskii, Andrey Mustafa, Nabil H. Pach, János |
| Copyright Year | 2017 |
| Abstract | Following groundbreaking work by Haussler and Welzl (1987), the use of small-nets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest-nets for set systems, as a function of their so-called shallow-cell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R 4 by a family of half-spaces such that the size of any-net for them is Ω(1 log 1) (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to half-spaces in R d , for any d ≥ 4, to show that the general upper bound, O(d log 1), of Haussler and Welzl for the size of the smallest-nets is tight. |
| Starting Page | 527 |
| Ending Page | 541 |
| Page Count | 15 |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/978-3-319-44479-6_21 |
| Alternate Webpage(s) | https://hal.archives-ouvertes.fr/hal-01468669/file/epsnetslowerbounds012717.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/978-3-319-44479-6_21 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
