The diameter of Voronoi cells in Euclidean spaces

Question

Let $A \subset \mathbb{R}^d$ and let $(x_n)_{n \in \mathbb{N}} \subset \mathbb{R}^d$ be a sequence dense in $A$. For each $n \in \mathbb{N}$, let $V_{1,n},\dots,V_{n,n}$ the sequence of Voronoi cells associated to the points $x_1, \dots, x_n$, where the ties are broken lexicographically, i.e.: $$V_{1,n} =\{x \in \mathbb{R}^d \mid \forall k\in\{2,\dots,n\}, |x-x_1|\le |x-x_k|\} \\ V_{2,n} =\{x \in \mathbb{R}^d \mid |x-x_2|<|x-x_1| \land \forall k\in\{3,\dots,n\}, |x-x_2|\le |x-x_k|\} \\ \vdots \\ V_{n,n} =\{x \in \mathbb{R}^d \mid \forall k\in\{1,\dots,n-1\}, |x-x_n| < |x-x_k|\} $$ If $x \in \mathbb{R}^d$ and $n \in \mathbb{N}$, define $V_n(x)$ as the unique element in $V_{1,n},\dots, V_{n,n}$ that contains $x$.

Is it true that $$\forall x \in A, \operatorname{diam}\big(A \cap V_n(x)\big) \to 0, n \to \infty?$$

I suspect that this result should hold due to the finite dimensionality of $\mathbb{R}^d$, since at least in this case we can obtain bounded sets using a finite number of intersections of half-spaces. However, it seems quite involved from a geometric point of view to obtain this claim. Has anyone any idea?

EDIT: note that we can WLOG assume that $A$ is the closure of the set whose points are those of the sequence $(x_n)_{n \in \mathbb{N}}$.

Some context: I'm trying to prove the aforementioned result to obtain that if $g \colon A \to \mathbb{R}$ is a continuous function, then $$\forall x \in A, \sup_{y \in A \cap V_n(x)} |g(x) - g(y)| \to 0, n \to \infty.$$

Answer 1

For additional insight, one key intuition might be that, by definition of density, any part of the set will eventually be dotted by an arbitrarily fine cloud of points.

Note that the definition of $ V_n $ is to choose among $ V_{1,n} \cdots V_{n,n} $ with $ n $ points present from the start. Sufficiently far down the sequence, there should be points arbitrarily close to $ x $ “all around” in order to “force” $ V_n $ into an arbitrarily small corner.

Otherwise, some angle would remain open, in which an open ball could exist, the interior of which must intersect a region of $ A $ where the sequence could then not be dense.

Edit: I see now that this is already plain for the particular case $ A = \mathbb{R}^d $, but does not help understanding what happens when the cells are unbounded. Would it be fair to say you are asking why it is that the unboundedness must resolve when capping by $ A $?

It should be in principle easier to show that the diameter at least does not diverge to infinity. Any point in the sequence is eventually “surrounded” by other points “in the local directions of $ A $” as you so evocatively put it.

Consider any $ a \in A $ and its path connected component of $ A $, then any path emanating from it must encounter points of the sequence within an arbitrarily thin thickness and arbitrarily close to it. Therefore no “local direction” is ever free to go on forever.

This is far from rigorous, I hope it nevertheless contributes positively to the discussion.

Answer 2

Let $x\in A$ and fix any $\delta > 0$. If we show that $V_n(x) \cap A$ is eventually contained in $B_{\delta}(x)$ as $ n \to \infty$, then we also get $\operatorname{diam}\big(A \cap V_n(x)\big) \to 0$ since $\delta$ is arbitrary. We will thus try to show that this is true.

For every $\theta$ satisfying $0<\theta<\pi/4$, then using that $\partial B_{\delta}(x)$ is compact we can find a finite open covering $\{C_i\}_{i=1}^K$ of $\mathbb{R}^d-\{x\}$ where every $C_i$ is an open cone with vertex in $x$ and isometric to the cone: $$C=\{y\in \mathbb{R}^d \mid \lVert y \rVert \cos{\theta} <\langle y,e_1\rangle\}$$.

Claim 1: if $\theta$ is small enough, then we have $V_n(x) \cap A \cap C_i \subseteq B_{\delta}(x)$ holding eventually for every $i=1,\dots, K$. In particular, we will prove that it is sufficient to choose $\theta$ satisfying $\tan{\theta}=(2+4\sqrt{d})^{-1}$.

Let $1 \leq j \leq K$ and set $R:=\inf\{ \lVert x -y\rVert \mid y\in (A \cap C_j) \cap B_{\delta}(x)^c \}$

If $R=+\infty$, then $ (A \cap C_j) \subseteq B_{\delta}(x)$ and so $V_n(x) \cap A \cap C_j \subseteq B_{\delta}(x)$ for every $n$.

If $\delta \leq R < +\infty$, then up to an isometry we have $x=0$ and $C_j=C$. In this case, we set $R=(1+4\sqrt{d})\ell$ and consider the following subsets of $\mathbb{R}^d$: $$Q:=Re_1+ (-\ell,\ell)^d \qquad B:=B_{2\ell\sqrt{d}}(0)$$

If $(y_1,\hat{y}_1)\in C$ we have: $$ \lVert \hat{y}_1 \rVert < y_1 \tan{\theta} $$ So, if $R-\ell <y_1<R+\ell$ then in particular $y_1<R+\ell=(2+4\sqrt{d})\ell$ and we have $\lVert \hat{y}_1 \rVert < \ell$. This shows that: $$C\cap Q = C \cap \{ (y_1,\hat{y}_1)\in \mathbb{R}^d \mid R-\ell <y_1<R+\ell\},$$ and the definition of $R$ entails that $A \cap Q \cap C\ \neq \emptyset$.

We fix now an arbitrary $u \in A \cap Q \cap C$, we fix $v \in B$ and set $$S=S(u,v)=\{z\in \mathbb{R}^d \mid \lVert u - z \rVert <\lVert v - z \rVert \}.$$

Claim 2: $Q \cup \{ (y_1,\hat{y}_1)\in C \mid y_1 \geq R +\ell\}\subset S$.

Suppose first $z \in Q$. We have $\operatorname{diam}(Q)=2\ell \sqrt{d}$ and so $\lVert u-z \rVert < 2\ell \sqrt{d}$ since $Q$ is an open hypercube. so we have: $$\lVert v - z \rVert > \operatorname{dist}(B,Q)=R-\ell-2\ell\sqrt{d}=2\ell\sqrt{d}$$ showing $z \in S$ in this case. If $z \in \{ (y_1,\hat{y}_1)\in C \mid y_1 \geq R+\ell\}$ we argue by contradiction: $0 \in S^c$ and if also $z\in S^c$, then by convexity of both $C$ and $S^c$ we would get $Q\cap S^c\neq \emptyset$, but this is impossible. We conclude that also in this case $z\in S$. This proves Claim 2.

Now, suppose that $V_n(x)$ is the Voronoi cell associated to a certain element of the sequence $x_m \in B$ and that for an index $p\leq n$ we have that the element of the sequence $x_p \in A \cap Q \cap C$. This is possible if $n$ is sufficiently large due to density of the sequence $(x_n)_n$ in $A$.

If $z \in A \cap C \cap B_{\delta}(0)^c$, by definition of $R$, either $z\in Q$ or $\langle z,e_1\rangle \geq R+\ell$. But then $z\in S(x_p,x_m)$ and thus $z \notin V_n(x)$.

Therefore $V_n(x) \cap A \cap C_j \subseteq B_{\delta}(x)$ holds eventually and so $V_n(x) \cap A \cap C_i \subseteq B_{\delta}(x)$ holds for every $1\leq i \leq K$ eventually (we have to take $n$ as the maximum of the $K$ indices that the argument produces for every possible value of $j$). This proves Claim 1, which is equivalent to $V_n(x) \cap A \subseteq B_{\delta}(x)$ eventually.