Jean-Daniel Boissonnat
email: jean-daniel.boissonnat@inria.fr

Ramsay Dyer
email: ramsay.dyer@inria.fr

Arijit Ghosh

Nikolay Martynchuk
email: n.martynchuk@rug.nl

An obstruction to Delaunay triangulations in Riemannian manifolds

Keywords: Delaunay complex, triangulation, Riemannian manifold MSC2010: 57R05 (Primary) 54B15, 53B20 (Secondary)

Delaunay has shown that the Delaunay complex of a finite set of points P of Euclidean space R m triangulates the convex hull of P , provided that P satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay's genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on P are required. A natural one is to assume that P is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.

Delaunay complex and Delaunay triangulation

Let (M, d M ) be a metric space, and let P be a finite set of points of M. An empty ball is an open ball in the metric d M that contains no point from P . We say that an empty ball B is maximal if no other empty ball with the same centre strictly contains B. A Delaunay ball is a maximal empty ball.

A simplex σ is a Delaunay simplex if there exists some Delaunay ball B that circumscribes σ, i.e., such that the vertices of σ belong to ∂B ∩ P . The Delaunay complex is the set of Delaunay simplices, and is denoted Del M (P ). It is an abstract simplicial complex and so defines a topological space, |Del M (P )|, called its carrier . We say that Del M (P ) triangulates M if |Del M (P )| is homeomorphic to M. A Delaunay triangulation of M is a homeomorphism H : |Del M (P )| → M.

The Voronoi cell associated with p ∈ P is given by

V M (p) = {x ∈ M | d M (x, p) ≤ d M (
x, q) for all q ∈ P }.

More generally, a Voronoi face is the intersection of a set of Voronoi cells: given σ = {p 0 , . . . , p k } ⊂ P , we define the associated Voronoi face as

V M (σ) = k i=0 V M (p i ).
It follows that σ is a Delaunay simplex if and only if V M (σ) = ∅. In this case, every point in V M (σ) is the centre of a Delaunay ball for σ. Thus every Voronoi face corresponds to a Delaunay simplex. The Voronoi cells give a decomposition of M, denoted Vor M (P ), called the Voronoi diagram. The Delaunay complex of P is the nerve of the Voronoi diagram.

In the case of R m equipped with the standard Euclidean metric, Delaunay [START_REF] Delaunay | Sur la sphère vide[END_REF] showed that, if P is generic, then the natural inclusion P → R m induces a piecewise linear embedding |Del R m (P )| → R m of the Delaunay complex of P into R m . This is called the Delaunay triangulation of P (it is a triangulation of the convex hull of P ). The point set P is generic if there is no Delaunay ball with more than m + 1 points of P on its boundary. Point sets that are not generic are often dismissed in theoretical work, because an arbitrarily small perturbation of the points will almost surely yield a generic point set [START_REF] Delaunay | Sur la sphère vide[END_REF]. In the sense of the standard measure in the configuration space R m×|P | , almost all point sets will yield a Delaunay triangulation.

A similar situation is known for certain standard non-Euclidean geometries, such as Laguerre geometry [START_REF] Aurenhammer | Power Diagrams: Properties, Algorithms and Applications[END_REF], spaces equipped with a Bregman divergence [BNN10], or Riemannian manifolds of constant sectional curvature1 .

Leibon and Letscher [LL00] announced sampling density conditions which would ensure that the Delaunay complex defined by the intrinsic metric of an arbitrary compact Riemannian manifold triangulates the manifold. When triangulating submanifolds of dimension 3 and higher in Euclidean space using Delaunay techniques, it was subsequently discovered that near degenerate "sliver" simplices pose problems which cannot be escaped simply by increasing the sampling density. In particular, developing an example on a 3-manifold presented by Cheng et al. [CDR05], Boissonnat et al. [BGO09, Lemma 3.1] show that, using the metric of the ambient Euclidean space restricted to the submanifold, the resulting Delaunay complex (called the restricted Delaunay complex ) need not triangulate the original submanifold, even with dense well-separated (no two points are too close) sampling.

Here we develop a similar example from the perspective of the intrinsic metric of the manifold. It can be argued that this is an easier way to visualize the problem, since we confine our viewpoint to a three dimensional space and perturb the metric, without referring to deformations into a fourth ambient dimension. This viewpoint also provides an explicit counterexample to the results announced by Leibon and Letscher [LL00]. We construct a fixed compact Riemannian manifold and demonstrate (Theorem 1) that for any sampling density there exists a point set that meets the sampling density and has good separation, but that does not admit a Delaunay triangulation, and furthermore, this property is retained when the point set is subjected to a sufficiently small perturbation. Thus, not only is there no sampling density that is sufficient to ensure the existence of a Delaunay triangulation on all compact Riemannian manifolds, but for any given fixed compact manifold, there may exist no sampling density that can guarantee a Delaunay triangulation. In particular, this latter property will complicate attempts to use Delaunay techniques in the construction and asymptotic analysis of optimal triangulations [Cla06, dL11].

Although we focus on the intrinsic metric, the same qualitative construction applies to the restricted ambient metric, demonstrating that the claim by Cairns [Cai61], that the Voronoi faces of the restricted Voronoi diagram are closed topological balls if the sampling is sufficiently dense, is also incorrect. In Section 3, we demonstrate a stable configuration in three dimensions in which the Voronoi face associated with a tetrahedron is two distinct points (0-balls), and the Voronoi face associated with an edge is two distinct topological 2-balls (see V M (uv) in Figure 3(a)). Since the restricted ambient metric is also qualitatively susceptible to this kind of construction, the Voronoi faces in the restricted metric are not necessarily themselves closed balls, regardless of the sampling density. This contradicts the natural interpretation of the statement that the Voronoi diagram "is a subdivision of [the manifold] into the closed cells of a complex" [Cai61]. However, our construction does not eliminate the possibility that the Voronoi faces are each collections of disjoint closed topological balls of the appropriate dimension. In this case, a generous interpretation of Cairns' result would hold, but it is not clear to us from Cairns' two-page note that the proof "is easy to complete".

The main purpose of this note is to clear up these persistent misconceptions that have appeared in the published literature.

A qualitative argument

As we show in this section with a qualitative argument, the problem can be viewed as arising from the fact that in a manifold of dimension m > 2, the intersection of two metric spheres is not uniquely specified by m points. We demonstrate the issue in the context of Delaunay balls. The problem is developed quantitatively in terms of the Voronoi diagram in Section 3.

We work exclusively on a three dimensional domain. The problem is a local one, and we are not concerned with "boundary conditions"; we are looking at a coordinate patch on a densely sampled compact 3-manifold.

One core ingredient in Delaunay's triangulation result [START_REF] Delaunay | Sur la sphère vide[END_REF] is that any triangle τ is the face of exactly two tetrahedra. This follows from the observation that a triangle has a unique circumcircle, and that any circumscribing sphere for τ must include this circle. The affine hull of τ cuts space into two components, and if τ ∈ Del R m (P ), then it will have an empty circumscribing sphere centred at a point c on the line through the circumcentre and orthogonal to aff(τ ). The point c is contained on an interval on this line which contains all the empty spheres for τ . The endpoints of the interval are the circumcentres of the two tetrahedra that share τ as a face.

The argument hinges on the assumption that the points are in general position, and on the uniqueness of the circumcircle for τ . If there were a fourth vertex lying on that circumcircle, then there would be three tetrahedra that have τ as a face; the third tetrahedron being the degenerate tetrahedron lying in aff(τ ), with all four vertices on the circumcircle of τ . But this configuration would violate the assumption of general position. Now if we allow the metric to deviate from the Euclidean one, no matter how slightly, the guarantee of a well defined unique circumcircle for τ is lost. In particular, if three spheres S 1 , S 2 and S 3 all circumscribe τ , their pairwise intersections will be different in general, i.e.,

S 1 ∩ S 3 = S 2 ∩ S 3 .
Although these intersections may be topological circles that are "very close" assuming the deviation of the metric from the Euclidean one is small enough, "very close" is not good enough when the only genericity assumption allows configurations that are arbitrarily bad.

The problem is illustrated in Figure 1, where τ = {u, v, p}. Here, circumspheres S 1 and S 2 of the Delaunay tetrahedra {a, u, v, p} and {u, v, p, b} would contain any empty sphere S 3 that circumscribes τ if the metric were Euclidean, but any aberration in the metric may leave a part of S 3 exposed to the outside. This means that in principle another sample point w could lie on S 3 , while S 1 and S 2 remain empty. Thus there would be a third Delaunay tetrahedron, {u, v, p, w} that shares τ as a face.

In dimension 2 this problem does not arise [Lei99, DZM08]. The essential difference between dimension 2 and the higher dimensions can be observed by examining the topological intersection properties of spheres. Specifically, two (m-1)-spheres intersect transversely in an (m-2)-sphere. For a non-Euclidean metric, even if this property holds for sufficently small geodesic spheres, it is only when m = 2 that the sphere of intersection of the Delaunay spheres of two adjacent m-simplices is uniquely defined by the vertices of the shared (m-1)-simplex.

An obstruction to intrinsic Delaunay triangulations

We now explicitly show how density assumptions alone cannot escape topological problems in the Delaunay complex. The configuration considered here may be recognised as similar to the In Euclidean space {u, v, p} defines a unique circumcircle (shown in black) that is the intersection of any two distinct spheres that circumscribe {u, v, p}, but if the metric deviates from Euclidean, this circle is no longer relevant; we can have three distinct spheres, S 1 , S 2 , and S 3 all circumscribing {u, v, p} and such that S 1 ∩S 3 = S 2 ∩S 3 . This means that {u, v, p} can be a face of three Delaunay tetrahedra, e.g., S 1 , S 2 and S 3 could be circumscribing spheres for {a, u, v, p}, {u, v, p, b}, and {u, v, p, w}, respectively. one described qualitatively in Section 2, but here we consider the Voronoi diagram rather than Delaunay balls. As before we work exclusively in a local coordinate patch on a densely sampled compact 3-manifold.

The idea is to consider four points in the xz-plane in Euclidean space, and show that with a mild perturbation of the metric, this tetrahedron exhibits exactly two distinct circumcentres. We construct a perturbed metric such that for any sampling density, a tetrahedron with two distinct Delaunay balls can exist. This means that the Delaunay complex, defined as the nerve of the Voronoi diagram, will not triangulate the manifold (this Delaunay tetrahedron will have two triangle faces that are not the face of any other Delaunay tetrahedron, as discussed below).

Delaunay's genericity condition [START_REF] Delaunay | Sur la sphère vide[END_REF] naturally extends to the setting where M is a manifold, and Leibon and Letscher [LL00, p. 343] explicitly assume genericity in this sense:

Definition 1 If M is a Riemannian m-manifold, the set P ⊂ M, is generic if no subset of m + 2 points lies on the boundary of a geodesic ball.

Delaunay only imposed the constraint on empty balls, and he showed that any (finite or periodic) point set in Euclidean space can be made generic through an arbitrarily small affine perturbation. That a similar construction of a perturbation can be made for points on a compact Riemannian manifold has not been explicitly demonstrated. However, in light of the construction we now present, it seems that the question is moot when m > 2, because an arbitrarily small perturbation from degeneracy will not be sufficient to ensure that a Delaunay triangulation exists.

For a point x in a compact Riemannian manifold M (without boundary), the injectivity radius at x is the supremum of radii r such that a geodesic ball with radius r, i.e., B M (x, r) = {y ∈ M | d M (x, y) < r}, has the property that each y ∈ B M (x, r) is connected to x by a unique minimising geodesic. The injectivity radius of M, denoted inj(M), is the infimum of We say P ⊂ M is -dense if d M (x, P ) < for any x ∈ M. If d M (p, q) ≥ ˜ for all p, q ∈ P , then P is ˜ -separated . The set P is an -net if it is -dense and -separated.

Theorem 1 For every integer m > 2 there exists a compact Riemannian m-manifold M such that for any > 0, with < inj(M)/2, there exists a generic -net P ⊂ M such that Del M (P ) does not triangulate M. Furthermore, this holds true for all perturbed point sets P ⊂ M that are within a small positive Hausdorff distance of P .

Proof. Consider 3-dimensional Euclidean space, parameterised by x, y, and z, to be the parameter domain of a coordinate chart of a compact Riemannian 3-manifold M. Place points u and v at ± a on the z axis, and points w and p at ± a(1 + ξ) on the x-axis. Here > 0 is the sampling parameter that parameterises the scale of the example, a = 1/ √ 2, and ξ > 0 is a small parameter that will be constrained by considerations below. We will fix a metric d M on M, and the value of ξ will depend on this metric, as well as the sampling parameter .

With this configuration, u and v will share a Voronoi face in the Euclidean metric which will extend indefinitely in the y-direction, but have a very short extent in the x-direction, assuming ξ is very small. Figure 2(a) depicts the slice of this Voronoi diagram defined by the xz-plane, as viewed from somewhere on the negative y-axis.

We now construct a metric on M such that the geodesic distance between u and v will be greater than the distance between p and w, thus qualitatively changing the structure of the Voronoi diagram in the xz-plane, as shown in Figure 2(b). To do this we employ a C ∞ nonnegative bump function f : R → R ≥0 that is symmetric: f (-y) = f (y), and satisfies f (y) ≤ 0 for y > 0 within our region of interest, and a strict inequality f (y) < 0 for y > 0 in some open neighbourhood of the origin. Thus there is a unique maximum at the origin. As an explicit example, we may assume that the underlying set of M is the torus R 3 /(2Z) 3 , and that f (y) = A(1 + cos(πy)), where the amplitude is constrained by A ≤ 3/8, as described below. We define the metric tensor of M in our coordinate system by

g(q) =   1 0 0 0 1 0 0 0 1 + f (y(q))   ,
where y(q) denotes the y-coordinate of the point q.

By integrating along the z-axis we obtain an upper bound on the geodesic distance between v and u:

d M (v, u) ≤ 2 a 0 (1 + f (0)) 1/2 dz = 2a (1 + f (0)) 1/2 . (1)
In fact, if the right hand side of (1) is less than the injectivity radius of M, then equality with d M (v, u) is attained. Indeed, in this case the curve represented by the z-axis is the minimising geodesic between v and u. This follows from the symmetry of the metric: the reflection through the xz-plane (x, y, z) → (x, -y, z) is an isometric involution that leaves points in the xz-plane fixed. Since an isometry maps geodesics to geodesics, and the minimising geodesic between v and u is unique, it must lie in the xz-plane, and, again by symmetry, the minimising curve is the straight line in the parameter domain.

We require that all four points lie within a ball centred at the origin, and with diameter less than inj(M). The final constraint that we impose on f is that f (0) ≤ 3/4. Another reason for this constraint is described below, but in particular it implies that a(1 + f (0)) 1/2 < 1. Then we see that, provided that < inj(M)/2,

d M (v, u) = 2a (1 + f (0)) 1/2 < inj(M).
(2)

We also require that d M (p, w) < d M (u, v), so that we have the qualitative Voronoi diagram in the xz-plane depicted by Figure 2(b). Observing that

d M (p, w) = d R 3 (p, w) = 2a (1 + ξ),
and equating with (2), we see that d M (p, w) = d M (u, v) if ξ is equal to the critical value defined by

ξ 0 = (1 + f (0)) 1/2 -1,
and so we require ξ < ξ 0 . The goal is to show that the tetrahedron σ = {u, v, w, p} can be a Delaunay tetrahedron admitting two distinct Delaunay balls in an -net P . To that end, we require that it has a circumcentre c on the positive y-axis, at a distance less than from the vertices (-c will also be a circumcentre). Let the y-coordinate of c be b . We argue that for any b > 0, there is a ξ < ξ 0 such that c = (0, b , 0) and -c are circumcentres of σ.

The geodesic distance between u and a given c is no greater than the geodesic length of the straight line between them in the parameter domain:

d M (u, c) ≤ b 0 (1 + f (y)) a 2 b 2 + 1 1 2 dy < b 0 (1 + f (0)) a 2 b 2 + 1 1 2 dy = b (1 + ξ 0 ) 2 a 2 b 2 + 1 1 2
.

(3) Also, the geodesic distance between u and c is greater than the Euclidean distance:

d M (u, c) > d R 3 (u, c) = b a 2 b 2 + 1 1 2
.

It follows then that for any b > 0, there exists a positive ξ(b) < ξ 0 such that

d M (u, c) = b (1 + ξ(b)) 2 a 2 b 2 + 1 1 2 . ( 4
)
Since d M (u, c) varies smoothly with b, ξ must be a smooth function.

The symmetry of the metric implies that the unique minimizing geodesic between p and c must lie in the xy-plane, where the metric coincides with the Euclidean one. It follows that, for p = (-(1 + ξ)a , 0, 0), we have

d M (p, c) = d R 3 (p, c) = b (1 + ξ) 2 a 2 b 2 + 1 1 2 . ( 5
)
Thus when ξ(b) = ξ we have d M (u, c) = d M (p, c), and it follows (by symmetry) that c is a circumcentre for σ.

We need to keep b small enough that d M (u, c) < , so that σ can be a Delaunay tetrahedron in an -net. It is sufficient to demand that b ≤ b max = a/2; then the fact that d M (u, c) < follows from the constraint f (0) ≤ 3/4 and the definitions a 2 = 1/2, and b 2 ≤ b 2 max = 1/8:

d M (u, c) < b (1 + f (0)) a 2 b 2 + 1 1 2 ≤ .
Also, it follows from the construction that the vertices of σ meet the separation criterion of an -net: geodesic distances between the points are bounded below by the Euclidean distances in the parameter domain, e.g., d M (u, w) > uw = a (1 + (1 + ξ) 2 ) 1/2 > . Thus, σ can be realised as a Delaunay simplex with exactly two distinct Delaunay balls in an -net. The configuration can be realised as part of an -net so that the two circumcentres of σ remain Voronoi vertices. Furthermore, this is not a degenerate configuration in the sense of Definition 1, because the requirements of an -net are met without placing any further vertices on the Delaunay spheres associated to σ; i.e., σ is not the proper face of any Delaunay simplex.

When we deviate from a Euclidean metric we can encounter degeneracies different from those described by Definition 1. For example, if we were to choose ξ = ξ 0 in our example, then σ would have a unique circumcentre (at the origin), and it could be a Delaunay simplex that is not the proper face of any other. But an arbitrarily small perturbation, sending u or v towards the origin, for example, would mean that σ has no circumcentre at all. However, at least for some positive b ≤ b max , the presented example is not degenerate in any strict sense: there is some number ρ > 0 such that the vertices of σ can be each independently displaced by a distance ρ without disturbing the combinatorial structure of the Voronoi diagram. In other words, this bad configuration is represented by a set of positive measure in the configuration space.

In order to demonstrate this it is sufficient to show that the circumcentres of σ depend continuously on the position of the vertices, at least in a neighbourhood of s 0 = (p, v, w, u). This can be shown by demonstrating that the origin is a regular value of the map

h : R 3 → R 3 q → d M (q, u) -d M (q, p), d M (q, v) -d M (q, p), d M (q, w) -d M (q, p) . (6)
Indeed, if this is the case, then the implicit function theorem applied to the function F : R 12 ×R 3 → R 3 defined by (6), such that F (s 0 , q) = h(q), ensures that for all vertex positions s in a neighbourhood of s 0 , there will be circumcentres (solutions to F (s, q) = 0) close to c and -c.

In order to estimate the Jacobian determinant of h at q = c, let H(q) = H(x, y, z) = d M (q, u)d M (q, p) be the first component of h, and observe that, by symmetry, H(x, y, -z) = V M (w) d M (q, v)d M (q, p) is the second component. Let W (q) = d M (q, w)d M (q, p) be the third component. We observe that W (q) = 0 if x(q) = 0. Therefore, denoting partial derivatives with subscripts, we have W y = W z = 0 at q = c. Also, we observe directly that W x is negative. Let W x (c) = t < 0. Therefore the Jacobian matrix has the form

V M (p) V M (uv) V M (uv)
Dh(c) =   H x H y H z H x H y -H z t 0 0   ,
and to show that its determinant is nonzero, we need to verify that H y and H z are nonzero at c. By inspection H z (c) < 0 since c is a critical point of d M (q, p) with respect to variation in the z direction, and d M (q, u) is strictly decreasing at c as q moves up a vertical line. For H y (c), we exploit the fact that we have explicit expressions, (4) and (5), that describe d M (u, c) and d M (p, c). When differentiating with respect to b at the point where ξ(b) = ξ, we find

H y (c) = ∂ b d M (c, u) -∂ b d M (c, p) = a 2 (1 + ξ) ξ ((1 + ξ) 2 a 2 + b 2 ) 1 2 . ( 7
)
Equation (3) shows that for any b > 0, we have ξ(b) < ξ 0 = ξ(0), and in particular, this is true for b = b max . So it follows from the mean value theorem that there is a b ∈ (0, b max ] such that ξ (b) < 0, and (7) implies that when ξ is chosen so that this b represents a cicumcentre, we have H y (c) < 0. Thus this configuration is stable with respect to small perturbations of the vertices. This constructed Delaunay tetrahedron σ with two distinct circumcentres implies a defect in the Voronoi diagram that prevents Del M (P ) from triangulating M. A schematic view of the Voronoi diagram associated with σ is depicted in Figure 3. The circumumcentres of σ are the Voronoi vertices shown in the diagram. A Voronoi edge corresponds to a Delaunay triangle, and the cofaces of the triangle are the Delaunay tetrahedra that correspond to the Voronoi vertices at the ends of the Voronoi edge. So for triangle t = {u, p, w}, since the Voronoi vertex at each end of V M (t) represents the same simplex, σ, there will be only one coface of t (likewise for triangle {v, p, w}). Since our manifold M has no boundary, Del M (P ) cannot triangulate M.

Finally, observe that this kind of counter-example to Delaunay triangulations will also exist in higher dimensional manifolds. For example, the same basic construction when m > 3 can be obtained by starting with a regular simplex σ of dimension (m -2) such that its circumcentre is at the origin, and its circumradius is a(1 + ξ), with a = 1/ √ 2, and such that

aff(σ) = {x ∈ R m | x m-1 = x m = 0}.
Then place two additional vertices at ±a on the x m-1 -axis to obtain an m-simplex. The metric g is then the diagonal matrix with g ii (q) = (1 + f (x m-1 (q))) if i = m and g ii (q) = 1 otherwise, and f defined exactly as before.

The qualitative construction of the previous section (Figure 1) is similar to the one we have considered here except that it conceptually employs a different perturbation function, whose support need not be symmetric with respect to the xz-plane, so that the simplex {u, v, p, w} can be dual to a single stable Voronoi vertex. The Delaunay perspective on the example represented in Figure 3 would be similar to Figure 1, except that there would be two distinct green Delaunay balls for σ.

Discussion

We have shown that for constructing a Delaunay triangulation of an arbitrary compact Riemannian manifold, a sampling density requirement is not sufficient in general. One approach to this problem might be to constrain the kind of metrics that are considered. However, the example shown here exhibits a problem even with a mild deviation from homogeneity, so the admissible metrics will be severely limited. We expect this kind of problem to arise any time one attempts to contruct an anisotropic triangulation using the empty sphere property in dimension m > 2, unless the (m-1)-spheres circumscribing m points are constrained to all intersect in a unique (m-2)-sphere defined by those points.

For example, in the anisotropic framework studied by Canas and Gortler [CG12] in the 2-dimensional setting, we can in three dimensions construct a problematic configuration as discussed in Section 2. In this setting, the "metric" is no longer symmetric, but the Delaunay triangulation is still described by the empty ball property; the balls are ellipsoids defined by the quadratic form associated with the centre. We can construct three ellipsoids that each have τ = {u, v, p} on their boundary, and such that the problem of three Delaunay tetrahedra that have τ as a face occurs in qualitatively the same way as in Figure 1. The Delaunay complex in this setting is still defined as the nerve of the Voronoi diagram, so a quantitative example analogous to that presented in Section 3 could also be constructed. In our obstruction the full dimensional Voronoi cells are connected ("orphan free"), as is always the case in the Riemannian metric. This is a topological obstruction to an embedding of this anisotropic Delaunay complex in R 3 . (Even when the topology of the complex is correct, the natural piecewise linear map into Euclidean space defined by the coordinates of the vertices may not be an embedding, i.e., some simplices may be "inverted"; see [CG15, Figure 16, Section 7]. Our construction in this note does not shed light on this kind of geometric problem.)

An alternate approach to avoiding the problematic topological obstructions to triangulation is to constrain the kinds of point sets considered. Pursuing this direction, we developed the notion of protected Delaunay balls in Euclidean space [BDG13], which provides a parameter that allows us to quantify how close a point set is to degeneracy. We showed that point sets with a positive bound on this parameter can be produced, and used this to construct an algorithm which, when given a sufficiently dense point set P on an arbitrary compact Riemanian manifold M, will produce a Delaunay complex Del(P ) which triangulates M and whose vertices P are a perturbation of the original point set P; see [BDG17].

Figure 1 :

 1 Figure1: In three dimensions, three closed geodesic balls can all touch three points, u, v, p, on their boundary and yet no one of them is contained in the union of the other two. In Euclidean space {u, v, p} defines a unique circumcircle (shown in black) that is the intersection of any two distinct spheres that circumscribe {u, v, p}, but if the metric deviates from Euclidean, this circle is no longer relevant; we can have three distinct spheres, S 1 , S 2 , and S 3 all circumscribing {u, v, p} and such that S 1 ∩S 3 = S 2 ∩S 3 . This means that {u, v, p} can be a face of three Delaunay tetrahedra, e.g., S 1 , S 2 and S 3 could be circumscribing spheres for {a, u, v, p}, {u, v, p, b}, and {u, v, p, w}, respectively.

  Metric of M.

Figure 2 :

 2 Figure 2: A qualitative schematic of a vertical slice (the y = 0 plane) of the Voronoi diagram, seen from the negative y axis (the axes are indicated in the lower left of the figures). In this plane the Euclidean diagram (a) is qualitatively different from the diagram (b) defined by the metric d M of M.

Figure 3 :

 3 Figure 3: Looking at cross-sections; the positive y-direction is to the right (the axes are indicated in the lower left of the figures). The tetrahedron σ = {p, u, v, w}, admits exactly two small circumballs with distinct centres (the red and blue points).

This is standard folklore. We are not aware of a published reference.

Acknowledgements

We thank Gert Vegter for suggesting that we look for an obstruction that can exist at all scales. We also thank David Cohen-Steiner and Mathijs Wintraecken for illuminating discussions.

This research has been partially supported by the 7th Framework Programme for Research of the European Commission, under FET-Open grant number 255827 (CGL Computational Geometry Learning). Partial support has also been provided by the Advanced Grant of the European Research Council GUDHI (Geometric Understanding in Higher Dimensions).

Arijit Ghosh is supported by Ramanujan Fellowship number SB/S2/RJN-064/2015. Part of this work was done when he was a researcher at the Max-Planck-Institute for Informatics, Germany supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Part of this work was also done while he was a visiting scientist at the Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India.