Covering and packing with homothets of limited capacity

arXiv2211.09328MaRDI QIDQ6417543FDOQ6417543

Oriol Solé-Pi

Publication date: 16 November 2022

Abstract: This work revolves around the two following questions: Given a convex body $Csubsetmathbb{R}^d$, a positive integer $k$ and a finite set $Ssubsetmathbb{R}^d$ (or a finite Borel measure $mu$ on $mathbb{R}^d$), how many homothets of $C$ are required to cover $S$ if no homothet is allowed to cover more than $k$ points of $S$ (or have measure larger than $k$)? How many homothets of $C$ can be packed if each of them must cover at least $k$ points of $S$ (or have measure at least $k$)? We prove that, so long as $S$ is not too degenerate, the answer to both questions is $Thet{a}_d(frac|S|k)$, where the hidden constant is independent of $d$. This is optimal up to a multiplicative constant. Analogous results hold in the case of measures. Then we introduce a generalization of the standard covering and packing densities of a convex body $C$ to Borel measure spaces in $mathbb{R}^d$ and, using the aforementioned bounds, we show that they are bounded from above and below, respectively, by functions of $d$. As an intermediate result, we give a simple proof the existence of weak $epsilon$-nets of size $O(frac1epsilon)$ for the range space induced by all homothets of $C$. Following some recent work in discrete geometry, we investigate the case $d=k=2$ in greater detail. We also provide polynomial time algorithms for constructing a packing/covering exhibiting the $Thet{a}_d(frac|S|k)$ bound mentioned above in the case that $C$ is an Euclidean ball. Finally, it is shown that if $C$ is a square then it is NP-hard to decide whether $S$ can be covered using $frac|S|4$ squares containing $4$ points each.

This page was built for publication: Covering and packing with homothets of limited capacity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6417543)