Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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... –  J. Martel 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) –  Dror Atariah 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. –  Łukasz Grabowski 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. –  Misha Aug 14 '13 at 21:35
And also mathoverflow.net/questions/43709 and references therein. –  Misha Aug 14 '13 at 21:37
add comment

1 Answer

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.

share|improve this answer
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 –  Łukasz Grabowski 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. –  Dror Atariah Aug 14 '13 at 6:59
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.