# Voronoi cells and the dual complexes in Riemannian manifolds

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

• I don't think one can ever expect the cells to be smooth submanifolds, i.e. for generic metrics and sets S the cells will have corners. But i have no proof...
– JHM
Aug 13 '13 at 21:28
• You might want to have a look at the so-called "nerve theorem" -- See Handbook of Combinatorics, Vol.2, Ch. 34, Theorem 10.7 (tinyurl.com/o8n7xll) Aug 14 '13 at 7:17
• Dror, many thanks for this reference. It seems the versions of the nerve theorem there are sufficiently general that, provided Questions 1 and 2 are answered, they will provide the answer to Question 3. Aug 14 '13 at 9:06
• Also, take a look at S. S. Cairns, A simple triangulation method for smooth manifolds, Bull. Amer. Math. Soc. 67 (1961), 389-390. Instead of the intrinsic metric he uses the extrinsic one, obtained from an embedding to the Euclidean space. For many purposes, this will suffice. Aug 14 '13 at 21:35
• This is not an answer but I think might be relevant. This reference shows that even for very dense sets of points in a Riemannian manifold of dimension 3 the dual of the Voronoi tesselation can fail to triangulate the manifold: arxiv.org/abs/1612.02905 Jun 18 '17 at 13:44

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.

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.

• Thanks Vidit, however I'm somewhat suspicious towards this reference because many of the claims are supposed to be in reference [9] Submitted for publication (2000), which seems not to be available. Also, I'll modify the first question because I'm still courious whether the intersections are manifolds Aug 13 '13 at 20:32
• In the past I tried to contact Leibon and Letscher and couldn't get any reply. I cannot point exactly, but as far as I know there are some serious flaws in the cited paper. Aug 14 '13 at 6:59

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.