2022/11/17 by Oriol Solé Pi, Pi, Oriol Solé
Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2211.09328
openalex publication_date 2022/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work revolves around the two following questions: Given a convex body C⊂ℝd, a positive integer k and a finite set S⊂ℝd (or a finite Borel measure μ on ℝ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 Θd((|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 ℝ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 ε-nets of size O(\frac1ε) 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 Θd((|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 (|S|)/(4) squares containing 4 points each.