Covering of a compact set

Question

Let $K$ be a compact subset of $\mathbb{R}^n$. Fix a constant $r>0$, I'm wondering whether there exists a finite collection of points $x_1,\dots,x_k \in K$ such that the collection of open balls $\{B(x_i,2r)\}_{i=1}^{k}$ forms an open cover of $K$ while $B(x_i,r)$ are mutually disjoint. I am looking for some variations of covering lemmas in $\mathbb{R}^n$ but failed to find any. Any insight or familiarity with would be appreciated.

minor correction: you probably mean $x_1, \ldots, x_{{\color{red} k}} \in K$. — Aryaman Maithani, Jul 11 '20 at 21:37

Jonathan Hole · Accepted Answer · 2020-07-12T01:34:07.087

8

Choose $N>0$ such that $K\subset [-N,N]^n$ and consider collections of disjoint balls with radii $r$ that are centered in $K$. All such balls have the same positive volume and are contained in the set $[-N-r,N+r]^n$ which has finite volume. Hence there is a (finite) upper bound on how many balls such collections can contain. This means that there is a maximal collection, say $\{B(x_1, r), \ldots ,B(x_n, r)\}$, with the above property. If the $B(x_i, 2r)$ did not cover $K$ this would be a direct violation of maximality.

edited Jul 12 '20 at 01:34

answered Jul 11 '20 at 23:55

Jonathan Hole

3,564

A variant of this is to let $C={B(y_i,r): 1\le i\le n}$ be a finite cover of $K$ and let $D={B(y_i,r):i\in V}$ be a maximal pairwise-disjoint subset of $C.$ Any $p\in K \cup D)$ \ $K$ must satisfy $d(p,x_i)<2r,$ otherwise $D$ would not be maximal. So ${B(x_i,r): i\in V}$ covers $K.$ – DanielWainfleet Jul 12 '20 at 03:53
The middle sentence of my comment above should be: Any $p\in K \setminus \cup D$ must satisfy $d(p,x_i)<2r$ for some $i\in V$, otherwise $D$ would not be maximal. – DanielWainfleet Jul 12 '20 at 04:11

score 3 · Answer 2 · answered Jul 11 '20 at 22:30

Let $K$ be a compact metric space.

The set $\mathscr X$ of sets $X\subseteq K$ woth the property $$ \forall x,y\in X\colon x\ne y\to d(x,y)\ge 2r$$ is partially ordered by inclusion. The union of a chain in $\mathscr X$ is also $\in\mathscr X$. Hence Zorn's lemma applies and so let $M\in\mathscr X$ be maximal. Suppose there is $a\in K$ with $a\notin\bigcup_{x\in M}B(x,2r) $. Then $M\cup\{a\}\in\mathscr X$, contradicting maximality of $M$.

Finally, by compactness of $K$, there is a finite subset $M_0$ of $M$ such that the $B(x,2r)$ with $x\in M_0$ still cover.

Kosh · Answer 3 · 2020-07-12T11:58:24.830

A side remark. A more geometric construction gives better results up to dimension $3$. You don't need the set to be compact. Bounded is sufficient.

Cover the bounded ($2d$) set $K$ by a finite number of squares of side $2r$ with pairwise disjoint interiors. Consider the open balls of radius $r$ concentric with the squares. These balls are disjoint, and the corresponding concentric balls of radius $\sqrt{2}\,r+\delta$ include the squares for any $\delta >0$. Hence, they cover the bounded set. In dimension three you get $\sqrt{3}\,r+\delta$.

Different tessellations of $\mathbb{R}^n$ can give what you ask in dimensions greater than 3 (with constants better than $2$).

I guess that one working on tessellations can figure out (maybe even easily) a formula $\rho(n)$, increasing in $n$, such that $\rho(n)\to 2$ when $n\to\infty$.

Covering of a compact set

3 Answers3