REAL

Coverings: Variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl

Frankl N, and Nagy J, and Naszódi, Márton (2018) Coverings: Variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl. DISCRETE MATHEMATICS, 341 (3). pp. 863-874. ISSN 0012-365X

[img] Text
FranklNagyNaszodi_Covering2018.pdf
Restricted to Repository staff only

Download (381kB) | Request a copy
[img]
Preview
Text
1607.02888.pdf

Download (415kB) | Preview

Abstract

We consider four problems. Rogers proved that for any convex body K, we can cover R-d by translates of K of density very roughly d ln d. First, we extend this result by showing that, if we are given a family of positive homothets of K of infinite total volume, then we can find appropriate translation vectors for each given homothet to cover R-d with the same (or, in certain cases, smaller) density. Second, we extend Rogers' result to multiple coverings of space by translates of a convex body: we give a non-trivial upper bound on the density of the most economical covering where each point is covered by at least a certain number of translates. Third, we show that for any sufficiently large n, the sphere S-2 can be covered by n strips of width 20n/ln n, where no point is covered too many times. Finally, we give another proof of the previous result based on a combinatorial observation: an extension of the Epsilon-net Theorem of Haussler and Welzl. We show that for a hypergraph of bounded Vapnik-Chervonenkis dimension, in which each edge is of a certain measure, there is a not-too large transversal set which does not intersect any edge too many times. (C) 2017 Elsevier B.V. All rights reserved.

Item Type: Article
Additional Information: Megjegyzés-27158757 N1 Funding details: 200020-162884, SNF, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung N1 Funding details: 200021-175977, SNF, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung N1 Funding text: M.N. thanks the support of János Pach's Chair of Discrete and Computational Geometry at EPFL, partly supported by the Swiss National Science Foundation grants Nos. 200020-162884 and 200021-175977. M.N. was also supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences, the National Research, Development, and Innovation Office, NKFIH Grant PD-104744 and by the ÚNKP-17-4 New National Excellence Program of the Ministry of Human Capacities. The three authors were supported by the National Research, Development, and Innovation Office, NKFIH Grant K119670. Part of this work is part of the MSc thesis of N. Frankl.
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 22 Sep 2019 14:26
Last Modified: 22 Sep 2019 14:26
URI: http://real.mtak.hu/id/eprint/100301

Actions (login required)

Edit Item Edit Item