REAL

New lower bounds for ε-nets

Kupavskii, A. and Mustafa, N.H. and Pach, János (2016) New lower bounds for ε-nets. In: Coloring Points with Respect to Squares. Leibniz International Proceedings in Informatics (LIPIcs) . Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, 54.1-54.16. ISBN 978-3-95977-009-5

[img]
Preview
Text
epsnetslowerbounds120215.pdf

Download (590kB) | Preview

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, Könemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in double-struck R4 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 double-struck Rd, 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. © Andrey Kupavskii, Nabil H. Mustafa, and János Pach.

Item Type: Book Section
Additional Information: N1 Funding Details: 15-01-03530, RFBR, Russian Foundation for Basic Research N1 Funding Details: 200020-14453, SNSF, Swiss National Science Foundation N1 Funding Details: 200020-144531, SNSF, Swiss National Science Foundation N1 Funding Details: 200020-162884, SNSF, Swiss National Science Foundation N1 Funding Details: 200021-137574, SNSF, Swiss National Science Foundation N1 Funding Details: JCJC-14-CE25-0016-01, ANR, Agence Nationale de la Recherche A4 et al.; National Science Foundation (NSF); Princeton University; The Center for Geometry and its Applications (SRC-GAIA); The Fields Institute for Research in Mathematical Sciences; Tufts University
Uncontrolled Keywords: GEOMETRY; Upper Bound; Shallow cells; Set system; Learning theory; Half spaces; General upper bound; Extremal problems; Set theory; Computational geometry; ε-nets; Shallow-cell complexity; LOWER BOUNDS; Half-spaces; Geometric set systems
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 03 Jan 2017 19:08
Last Modified: 03 Jan 2017 19:08
URI: http://real.mtak.hu/id/eprint/44231

Actions (login required)

Edit Item Edit Item