# When does a metric space admit finite covers by Voronoi diagrams of Delone sets?

Some preliminary definitions: For a given metric space $(X,d)$ and set $A\subset X$, the Voronoi diagram of $A$ (which I'll write $V(A)$) is the collection of sets of the form $$C_a=\{x\in X|\forall b\in A(a\neq b\rightarrow d(x,a)<d(x,b))\}$$ for each $a\in A$. A set $C_a$ is called a Voronoi cell. Note that except in 'trivial' cases $\cup V(A)=\bigcup_{a\in A}C_a\neq X$.

A set $A\subset X$ is an $\varepsilon$-net if $\bigcup_{a\in A}B_\varepsilon (a)=X$, where $B_\varepsilon (a)$ is the closed ball of radius $\varepsilon$ centered at $a$, although I don't think closed vs. open ball matters too much for this question. $A$ is uniformly discrete if there exists an $\varepsilon >0$ such that for any $a,b\in A$, $a\neq b$ implies that $d(a,b)\geq \varepsilon$. $A$ is a Delone set if it is uniformly discrete and an $\varepsilon$-net for some $\varepsilon>0$.

My question is: For which metric spaces $X$ does there exist a sequence of Delone sets $A_{n,i}\subset X$, with $n,i\in\mathbb{N}$ and $1\leq i\leq k_n$, such that for each $n$ $$\bigcup_{i=1}^{k_n}\left[ \cup V(A_{n,i})\right]=X$$ and for each $n$ and each $i$ $A_{n,i}$ is a $2^{-n}$-net?

This is clearly possible for $\mathbb{R}^m$, for instance, but since the number of required Delone sets for each $n$ grows like $m$ I suspect this may be impossible in any infinite dimensional Banach space. So I was wondering if this would be possible for things that are 'locally finite dimensional' like $\mathbb{R}$-trees or if maybe this is a really strong condition and implies local compactness or something like that.

• Your $\varepsilon$-coverings usually called $\varepsilon$-nets. – Anton Petrunin Apr 30 '17 at 21:29
• I was going from the definitions on this Wikipedia article where an $\varepsilon$-net needs to be an $\varepsilon$-cover as well as an $\varepsilon$-packing, but here I'm just requiring that the sets be a $\delta$-packing for some positive $\delta\leq\varepsilon$. – James Hanson May 1 '17 at 1:07
• these are not standard as far as I see, they say "ε-net" instead of "maximal ε-packing". – Anton Petrunin May 3 '17 at 3:40
• Ah ok. I changed the question. – James Hanson May 3 '17 at 18:15