Voronoi cells and the dual complexes in Riemannian manifolds

Question

I would like to use some "intuitively clear" properties of Voronoi cells in general Riemannian manifolds, but I have trouble finding references.

Let $(X,d)$ be a connected Riemannian manifold and let $S$ be a discrete set of points. Define $Vor(s,S) = \{x\in X\colon \text{for any $s'\in S$ we have } d(x,s) \le d(x,s')\}$.

Assume $S$ is such that for any $s\in S$ there is a finite subset $N(s)\subset S$ such that $Vor(s,S) = Vor(s,N(s))$.

Question 1. Is it true that $Vor(s,S)$ are submanifolds with a boundary, and the intersection of any number of them is a submanifold with a boundary?

Question 2. Under what general conditions $Vor(s,S)$ induce a structure of a CW-complex on $X$?

In general, define the dual $2$-complex $\hat X_2$: the vertices are $S$, there is an edge between $s$ and $s'$ if $Vor(s,S)\cap Vor(s',S)$ is of codimension $1$ in X and there is a face spanned by a finite subset $F \subset S$ if $F$ is a maximal subset such that the cells $Vor(f,S), f\in F$ share a codimension-2 submanifold.

Perhaps this ad-hoc definition of the dual complex is obviously flawed, in which case I'd appreciate references to a better one. To me it is not even immediately clear $\hat X_2$ is a CW complex i.e. if the boundary of a face is in the $1$-skeleton.

Question 3. Is it the case that if $X$ is contractible then $\pi_1(\hat X_2) =\{1\}$? (or if not, under what assumptions is it the case?)

Remark: In the previous version of Question 1 I asked whether the intersections are a connected manifolds. Vidit Nanda below provided an example which shows that it's not always the case

Answer 1

I don't have complete answers to your questions, but I want to point out that an assumption about the density of the sample set $S$ will not be sufficient to ensure that the Voronoi diagram induces a CW structure on $X$. Specifically, for a finite set $\sigma \subset S$, we define \begin{equation*} \mathrm{Vor}(\sigma, S) = \bigcap_{s \in \sigma} \mathrm{Vor}(s,S). \end{equation*} Then if $\sigma$ contains more than one element, $\mathrm{Vor}(\sigma,S)$ need not be a closed topological ball.

To see this, let $X$ be a $3$-manifold, and in a coordinate chart consider the metric \begin{equation*} g(x) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 + f(x_2(x)) \end{pmatrix} \end{equation*} where $f$ is a symmetric bump function that depends only on the $x_2$-coordinate of $x$. Now place points $u$ and $v$ at $\pm a$ on the $x_3$-axis. If $p$ and $q$ are placed at $\pm (a+\xi)$ on the $x_1$-axis, then for some small $\xi > 0$ we will have $d(p,q)=d(u,v)$. If we decrease $\xi$ a little bit, then $\sigma = \{u,v,p,q\}$ will have exactly two circumcentres, located at equal distance from the origin on the positive and negative $x_2$-axis. By tuning $\xi$ we can ensure that these circumcentres are as close as desired to the origin, and this means that they could be $\mathrm{Vor}(\sigma,S)$ even when $S$ is a dense point set (choosing $a$ appropriate for any density assumption).

This example shows that the assertions in the conference paper by Leibon and Letscher mentioned by Vidit Nanda are incorrect. The similar claim made by Cairns in the 1961 note mentioned by misha is also incorrect, for the same qualitative reason: Even though he considered the ambient Euclidean metric restricted to an embedded submanifold, this problem of Delaunay simplices admitting two distinct Voronoi centres can still happen.

The constructed configuration is "nearly degenerate", but it is not degenerate in any strict sense: the bad configuration cannot be destroyed with an arbitrarily small perturbation. To avoid these kinds of problems the set $S$ must be subjected to another constraint beyond a simple density restriction.

Answer 2

At least partial answers to your first two questions can be found in the brief article called Delaunay triangulations and Voronoi diagrams for Riemannian manifolds by Leibon and Letscher available here.

Let's start with something basic: endow the $2$-torus with the usual metric inherited from $\mathbb{R}^3$ and assume that your point set $S$ consists of only two points: the "top" and "bottom" with respect to the usual height function. It is quite clear that the two Voronoi cells are homeomorphic to cylinders with boundary (negatively answering the first question), and their intersection consists of two disconnected circles (negatively answering the second). There is a picture (Fig 3) on Page 3 of the pdf linked above.

All you really need is that the point set $S$ be sufficiently dense in the manifold $X$. With this assumption in place, we have the following nice result (numbered according to the pdf above)

Theorem 4.2 If $S$ is sufficiently dense in $X$, then its Voronoi cells provide a CW decomposition of $X$.

"Sufficiently dense" in this context is relative to the strong convexity radius of $X$, see Definition 3.2.

Answer 3

Although this answers none of the OP's questions—and is in fact entirely tangential—some might enjoy this image from an earlier MO question, Delaunay triangulations and convex hulls:

---

          
^{Image from a Mathematica demonstration project written by Maxim Rytin.}

---