Better Sampling Bounds for
Restricted Delaunay Triangulations and a
Star-Shaped Property for Restricted Voronoi Cells

The restricted Delaunay triangulation (RDT) is a well-established way of generating good-quality triangulations on curved surfaces [23]. Researchers have developed a theory of surface sampling to determine how we should sample points on a surface to guarantee that an RDT (or a related triangulation) is a topologically correct and geometrically accurate approximation of the surface [1, 2, 3, 6, 10, 12, 13, 14, 15, 17, 16, 18, 20, 23, 24, 26, 31, 34, 35]. RDTs and this surface sampling theory have equipped geometers to rigorously prove the correctness of algorithms for surface reconstruction [20] and surface mesh generation [18].

Think of the RDT as a function that takes in two inputs: a smooth, closed (compact with no boundary) surface $\mathrm{\Sigma }\subset {ℝ}^3$ and a finite set $V\subset \mathrm{\Sigma }$ of points, called sites (or vertices of the RDT). The set $V$ is a sample or a point cloud. The output is a simplicial complex $𝒯$ whose vertices are $V$. The RDT $𝒯$ is a subcomplex of the three-dimensional Delaunay triangulation $\mathrm{Del}V$, but in typical usage $𝒯$ contains no tetrahedra; only triangles, edges, and the vertices $V$.

If $V$ is sufficiently dense, $𝒯$ is a (topological) triangulation of $\mathrm{\Sigma }$, which means that the underlying space of $𝒯$, written $|𝒯|={\bigcup }_{\tau \in 𝒯}\tau$, is homeomorphic to $\mathrm{\Sigma }$. This paper proves that a modest sampling requirement suffices to guarantee that homeomorphism.

What does it mean for $V$ to be “sufficiently dense”? Intuitively, there should be no large unsampled bare spots on $\mathrm{\Sigma }$. Ideally, sampling requirements are adaptive, as a denser spacing of sites is needed in regions where $\mathrm{\Sigma }$ has higher curvature or closely-spaced “parts” like fingers on a hand, but simple regions need few sites. Many provably good algorithms for surface reconstruction assume that $V$ is a so-called $ϵ$-sample of $\mathrm{\Sigma }$ (defined in Section 2), an adaptive sample in which a smaller $ϵ$ implies more sites, closer together.

One main result of this paper is that if $V$ is a $0.3245$-sample of $\mathrm{\Sigma }$, the underlying space of the RDT is homeomorphic to $\mathrm{\Sigma }$. Dey [20] proved the same for a $0.18$-sample. The new result reduces the number of sample points required by a factor of $3.25$ (the square of $0.3245/0.18$). Some well-known surface reconstruction algorithms such as the Crust [1] and Cocone [3] algorithms rely on identifying a superset of the RDT’s triangles then paring them down. Any substantial relaxation of their sampling requirements is good news for a broad swath of existing algorithms, and it helps to explain why they work well in practice.

As a point of comparison, Bjerkevik [5] shows that no proof will ever guarantee homeomorphism for $0.72$-samples, as there exist $0.72$-samples with multiple, topologically different, correct reconstructions. (This limitation holds also for smooth, closed curves in the plane.)

We define another adaptive sampling condition better suited to mesh generation, enabling stronger sampling bounds: we prove homeomorphism for what we call a $0.4132$-Voronoi sample. Cheng et al. [18] proved the same for a $0.09$-Voronoi sample; our result reduces the number of sample points required by a factor of $21$. Our bound implies better sampling bounds for existing surface meshing algorithms; it is this paper’s most important result.

Also of interest are the new techniques introduced here to obtain these bounds. In particular, for a $0.44$-sample or a $0.78$-Voronoi sample, the restricted Voronoi cell of each site $v\in V$ (defined in Section 2) is homeomorphic to a disk. Moreover, let $T_v\mathrm{\Sigma }$ denote the plane tangent to $\mathrm{\Sigma }$ at $v$; the orthogonal projection of $v$’s cell onto $T_v\mathrm{\Sigma }$ is star-shaped: a union of (infinitely many) line segments terminating at $v$. It seems a bit surprising that restricted Voronoi cells are better behaved with respect to coarse samples than restricted Voronoi vertices or edges, because the proofs by Dey [20] and Cheng et al. [18] use the soundness of the restricted Voronoi edges to establish the soundness of the restricted Voronoi cells. This paper reverses that sequence and, in my opinion, gets at the heart of the reasons why a restricted Voronoi cell is nicely shaped. Remarkably, the results about the Voronoi cells generalize to manifolds of higher dimension embedded in higher-dimensional spaces with no degradation in the bounds [32], although the homeomorphism result does not and cannot generalize to higher dimensions [16, 11, 9].

Not everyone gets excited by improved constants, but I advocate for the importance of tighter sampling theory for computational geometry – just as numerical analysts have devoted much effort to improving constants associated with quadrature rules, interpolation theory, and more. Strong bounds show that RDTs are useful, not merely theoretical.

The RDT is defined by dualizing a restricted Voronoi diagram, which will be our main object of study. Let $|pq|$ denote the Euclidean distance from $p$ to $q$; equivalently, the length of the line segment $pq$. Given a closed surface $\mathrm{\Sigma }\subset {ℝ}^3$ and a sample $V\subset \mathrm{\Sigma }$, the restricted Voronoi cell of a site $v\in V$ is $\mathrm{Vor}{|}_{\mathrm{\Sigma }}v=\{p\in \mathrm{\Sigma }:|pv|\le |pw|$ for all $w\in V\}$. Equivalently, ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v=\mathrm{\Sigma }\cap \mathrm{Vor}v$, where $\mathrm{Vor}v$ is $v$’s standard Voronoi cell in ${ℝ}^3$. The name “restricted Voronoi cell” means that ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ is the restriction of $\mathrm{Vor}v$ to the surface $\mathrm{\Sigma }$. See Figure 1.

A restricted Voronoi face is any nonempty intersection of one or more restricted Voronoi cells – i.e., $\mathrm{\Sigma }\cap F$ for some face $F$ in $\mathrm{Vor}V$. In particular, a restricted Voronoi vertex is the nonempty intersection of $\mathrm{\Sigma }$ with an edge in $\mathrm{Vor}V$; and a restricted Voronoi edge is the nonempty intersection of $\mathrm{\Sigma }$ with a polygonal $2$-face in $\mathrm{Vor}V$. Typically these entities are a single point and a (curvy) path on $\mathrm{\Sigma }$, respectively, but if $V$ is not dense enough, they may take on more pathological forms – e.g., a restricted Voronoi “edge” could be a cycle, a pair of disjoint paths, or even a $2$-dimensional blob. This paper aims to determine sampling conditions that eliminate such pathologies. The restricted Voronoi diagram ${\mathrm{Vor}|}_{\mathrm{\Sigma }}V$ is the cell complex containing all the restricted Voronoi faces (including the restricted Voronoi cells).

The Delaunay subdivision $\mathrm{Del}V$ is the polyhedral complex dual to the Voronoi diagram, and the restricted Delaunay subdivision ${\mathrm{Del}|}_{\mathrm{\Sigma }}V$ is the subcomplex of $\mathrm{Del}V$ dual to the restricted Voronoi diagram. That is, for each Voronoi face $F\in \mathrm{Vor}V$, let $W\subseteq V$ be the set of sites whose Voronoi cells include $F$ and let $F^{\ast }$ be the convex hull of $W$; we say that $F^{\ast }$ is the face dual to $F$. Then $\mathrm{Del}V=\{F^{\ast }:F\in \mathrm{Vor}V\}$. The restricted Delaunay subdivision contains the dual faces whose primal faces intersect $\mathrm{\Sigma }$; that is, ${\mathrm{Del}|}_{\mathrm{\Sigma }}V=\{F^{\ast }\in \mathrm{Del}V:F\cap \mathrm{\Sigma }\ne \mathrm{\varnothing }\}$. The restricted Voronoi face $f=F\cap \mathrm{\Sigma }$ has the same dual face as $F$, $f^{\ast }=F^{\ast }$. It is customary to subdivide the polyhedra in $\mathrm{Del}V$ into tetrahedra (in which case the duality is no longer strict); accordingly, we can subdivide the polygons in ${\mathrm{Del}|}_{\mathrm{\Sigma }}V$ into triangles and call it a restricted Delaunay triangulation. This paper’s results apply whether we do or don’t.

A crucial observation in the theory of surface sampling is that the sampling density necessary for accurate approximation is proportional to a field called the local feature size. The medial axis $M$ of $\mathrm{\Sigma }$, illustrated in Figure 2, is the closure of the set of all points in ${ℝ}^3$ for which the closest point on $\mathrm{\Sigma }$ is not unique. A medial ball is a ball whose center lies on $M$ and whose boundary intersects $\mathrm{\Sigma }$ (tangentially), but the interior of the ball does not. For any point $x\in \mathrm{\Sigma }$, there are one or two medial balls that have $x$ on their boundaries, called medial balls at $x$. One is inside $\mathrm{\Sigma }$. If there are two, the other is outside. If not, there is an open halfspace tangent to $\mathrm{\Sigma }$ at $x$, disjoint from $\mathrm{\Sigma }$, that we call a degenerate “medial ball.”

The local feature size function is $\mathrm{lfs}:\mathrm{\Sigma }\to ℝ$, $x\mapsto d(x,M)$ where $d(x,M)={\min }_{m\in M}|xm|$. We require that $\mathrm{\Sigma }$ is smooth in the sense that ${inf}_{x\in \mathrm{\Sigma }}\mathrm{lfs}(x)>0$. ($C^{1,1}$-continuity suffices.)

A finite point set $V\subset \mathrm{\Sigma }$ is an $ϵ$-sample of $\mathrm{\Sigma }$ if for every point $x\in \mathrm{\Sigma }$, there is a site $v\in V$ such that $|xv|\le ϵ\mathrm{lfs}(x)$. That is, the ball with center $x$ and radius $ϵ\mathrm{lfs}(x)$ contains at least one site. A finite $V\subset \mathrm{\Sigma }$ is an $ϵ$-Voronoi sample of $\mathrm{\Sigma }$ if $V\ne \mathrm{\varnothing }$ and for every site $v\in V$ and every point $x\in {\mathrm{Vor}|}_{\mathrm{\Sigma }}v$, $|xv|\le ϵ\mathrm{lfs}(v)$. That is, ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ is a subset of the ball with center $v$ and radius $ϵ\mathrm{lfs}(v)$. (Note that this condition implies the $ϵ$-small condition of Cheng et al. [18], though the converse is not true.) Only $ϵ$-samples are a well-known concept, but $ϵ$-Voronoi samples are nice because $\mathrm{lfs}(v)$ tends to give better sampling bounds than $\mathrm{lfs}(x)$.

Like the classical proofs [1, 18, 20], this paper’s homeomorphism proofs rely on the Topological Ball Theorem of Edelsbrunner and Shah [23]. Given a sample $V\subset \mathrm{\Sigma }$ of a closed surface $\mathrm{\Sigma }\subset {ℝ}^3$, this theorem states that $|\mathrm{Del}{|}_{\mathrm{\Sigma }}V|$ is homeomorphic to $\mathrm{\Sigma }$ if $\mathrm{\Sigma }$ and $V$ satisfy two properties. The closed ball property is that for each Voronoi face $F\in \mathrm{Vor}V$, $f=F\cap \mathrm{\Sigma }$ is either empty or a topological closed $(k-1)$-ball where $k$ is the dimension of $F$. That is,

1. A.

   for a Voronoi $3$-cell $F$, $f$ is a topological closed disk;

2. B.

   for a Voronoi $2$-face $F$, $f$ is a topological closed interval or $\mathrm{\varnothing }$;

3. C.

   for a Voronoi edge $F$, $f$ contains at most one point; and

4. D.

   for a Voronoi vertex $F$, $f=\mathrm{\varnothing }$.

If A–D hold, the generic intersection property is that for each $F\in \mathrm{Vor}V$, $\mathrm{int}f\subset \mathrm{int}F$ and $\mathrm{bd}f\subset \mathrm{bd}F$. In this definition, “interior” and “boundary” are interpreted by the rules of $(k-1)$-manifolds (for $f$) and $k$-manifolds (for $F$). (They are not the interior and boundary with respect to ${ℝ}^3$.) For a smooth $\mathrm{\Sigma }$, the generic intersection property holds if properties A–D hold and there is no face $F\in \mathrm{Vor}V$ and no point $x\in F\cap \mathrm{\Sigma }$ such that $F\subset T_x\mathrm{\Sigma }$. That is,

1. E.

   there is no point where $\mathrm{\Sigma }$ intersects a $2$-face of $\mathrm{Vor}V$ tangentially; and

2. F.

   there is no point where $\mathrm{\Sigma }$ intersects an edge of $\mathrm{Vor}V$ tangentially.

This paper is organized around proving that these conditions hold for a sufficiently dense sample $V$: properties A and E in Section 4, properties C and F in Section 5, and property B in Section 6. Property D ensures that ${\mathrm{Del}|}_{\mathrm{\Sigma }}V$ contains no polyhedra – only faces of dimension two or less. Property D cannot be enforced by dense sampling, but it can be enforced by an infinitesimal perturbation of $\mathrm{\Sigma }$ so that $\mathrm{\Sigma }$ intersects no Voronoi vertex. This perturbation is easy to simulate symbolically in software simply by treating each Voronoi vertex on $\mathrm{\Sigma }$ as if it were strictly inside $\mathrm{\Sigma }$ (when deciding which faces of $\mathrm{Del}V$ are in ${\mathrm{Del}|}_{\mathrm{\Sigma }}V$).

Unlike in Dey [20] or Cheng et al. [18], our proof of property A does not rely on property B or C. Property A holds for a $0.4401$-sample or a $0.7861$-Voronoi sample, whereas we prove property B only for a $0.3245$-sample or a $0.4132$-Voronoi sample. Property B (restricted Voronoi edges) is the bottleneck that determines our sampling requirements.

Some algorithms for triangulating surfaces guarantee topological correctness without RDTs, by other methods [4, 8, 19, 27, 29]. One alternative is to consider Voronoi diagrams with other distance metrics. Dyer, Zhang, and Möller [21, 22] and others [28, 7] use intrinsic distances within $\mathrm{\Sigma }$, also known as geodesic distances when $\mathrm{\Sigma }$ is smooth, to define intrinsic Voronoi diagrams that dualize to intrinsic Delaunay triangulations (IDTs). Advantages are that the Voronoi cells are trivially star-shaped, and the sampling requirements needed to guarantee a homeomorphic triangulation are mild [22]. But intrinsic distances on smooth surfaces are painful to compute [30]. Restricted Delaunay triangulations will probably remain popular as an easy alternative. So let us see how far we can push them.

For a smooth, closed surface $\mathrm{\Sigma }$ and a point $x\in \mathrm{\Sigma }$, let $T_x\mathrm{\Sigma }\subset {ℝ}^3$ denote the plane tangent to $\mathrm{\Sigma }$ at $x$. ($T_x\mathrm{\Sigma }$ passes through $x$; not necessarily through the origin.) Lemma 1, below, establishes a relationship between $T_x\mathrm{\Sigma }$ and $v$ for two nearby points $v,x\in \mathrm{\Sigma }$. This relationship prepares us to prove in Section 4 that under suitable sampling conditions, a restricted Voronoi cell is a topological disk with a star-shaped projection on its site’s tangent plane. Lemma 1 is surprisingly strong; the constant $\xi$ (as it is applied in Theorem 6) will likely be hard to beat.

Let $B$ and $B^{\prime }$ be the two open balls of radius $\mathrm{lfs}(v)$ tangent to $\mathrm{\Sigma }$ at $v$, and let $o$ and $o^{\prime }$ be their centers. As $B$ and $B^{\prime }$ are subsets of the open medial balls at $v$, they are disjoint from $\mathrm{\Sigma }$.

This section investigates sampling conditions that guarantee that (1) every restricted Voronoi cell has the topology of a closed disk (closed ball property A), (2) the projection of each restricted Voronoi cell onto its site’s tangent plane is star-shaped, and (3) no $2$-face in $\mathrm{Vor}V$ intersects $\mathrm{\Sigma }$ tangentially (generic intersection property E). Theorem 6 shows that a $0.78$-Voronoi sample suffices, and Corollary 9 shows that a $0.44$-sample suffices.

Consider a site $v\in V$, its Voronoi cell $\mathrm{Vor}v$, and its restricted Voronoi cell ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v=\mathrm{\Sigma }\cap \mathrm{Vor}v$. Let $\phi$ be the map that orthogonally projects ${ℝ}^3$ onto $T_v\mathrm{\Sigma }$. Note that $\phi (v)=v$.

Define a radial path to be a topological closed interval $\gamma \subset {\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ such that

1. 1.

   one endpoint of $\gamma$ is the site $v$,

2. 2.

   the other endpoint – call it $z$ – lies on the boundary of $\mathrm{Vor}v$,

3. 3.

   every point on $\gamma \setminus \{z\}$ lies in the interior of $\mathrm{Vor}v$, and

4. 4.

   ${\phi |}_{\gamma }$ is a homeomorphism from $\gamma$ to a line segment on $T_v\mathrm{\Sigma }$ with endpoints $v$ and $\phi (z)$, where ${\phi |}_{\gamma }$ denotes the restriction of $\phi$ to the domain $\gamma$.

We will see that under suitable sampling conditions, every point in ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ lies on exactly one radial path, except $v$ itself (Lemma 4). It follows that we can decompose ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ into radial paths such that no two share a point besides $v$ (Lemma 5). That is, if we remove $v$ from each radial path, then we have a partition of ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v\setminus \{v\}$ into paths. Therefore, $\phi ({\mathrm{Vor}|}_{\mathrm{\Sigma }}v)$ is star-shaped. Although ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ itself is not star-shaped, its decomposition into radial paths is a curvy variant of “star-shaped.” As the lengths of the projected radial paths vary continuously with their polar angles, ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ is homeomorphic to a closed disk (Theorem 6).

Let $N_v\mathrm{\Sigma }$ be the line normal to $\mathrm{\Sigma }$ at $v$ (orthogonal to $T_v\mathrm{\Sigma }$). Let $B$ and $B^{\prime }$ be the two open balls of radius $\mathrm{lfs}(v)$ tangent to $\mathrm{\Sigma }$ at $v$, and let $o$ and $o^{\prime }$ be their centers. Then $o,o^{\prime }\in N_v\mathrm{\Sigma }$.

The following lemma implies that if you are standing on the boundary of ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v$ and you walk toward $v$ on a radial path, you immediately enter the interior of $\mathrm{Vor}v$. (The proof of Lemma 4 develops this idea further.) It also implies generic intersection property E.

A restricted Voronoi vertex is a nonempty intersection of $\mathrm{\Sigma }$ with an edge in $\mathrm{Vor}V$. However, without suitable sampling conditions, such an intersection might contain many points, even infinitely many. This section describes sampling conditions that guarantee closed ball property C: an intersection of three distinct restricted Voronoi cells contains at most one point, thereby justifying the name “vertex.” Generic intersection property F comes as a byproduct. Lemma 10 shows that a $0.49$-Voronoi sample suffices, and Corollary 11 shows that a $0.33$-sample suffices (which follows from Lemmas 10 and 8). Both proofs are postponed to the full-length paper [32], as restricted Voronoi vertices are not the bottleneck limiting our homeomorphism theorems’ sample bounds. (Restricted Voronoi edges are the bottleneck; see Section 6.) Note that Cheng et al. [18] prove Lemma 10 for a $0.15$-Voronoi sample.

Theorem 6 and Corollary 9 give conditions under which restricted Voronoi cells are topological closed disks. Lemma 10 and Corollary 11 give conditions under which the intersection of three distinct restricted Voronoi cells is at most one point. What about an intersection of two distinct restricted Voronoi cells? That could be empty, a restricted Voronoi vertex, or a restricted Voronoi edge, the last being a nonempty intersection of $\mathrm{\Sigma }$ with a $2$-face of $\mathrm{Vor}V$. Under suitable sampling conditions, Lemma 17, below, guarantees closed ball property B: each restricted Voronoi edge is a topological interval.

The next six lemmas derive conditions in which an intersection ${\mathrm{Vor}|}_{\mathrm{\Sigma }}v\cap {\mathrm{Vor}|}_{\mathrm{\Sigma }}w$ is one interval or one isolated point. Lemma 15 applies to $0.32$-samples, whereas Lemma 16 applies to $0.41$-Voronoi samples, and Lemma 17 concludes both. Lemma 12 has no sampling requirements, only topological requirements; see the full-length paper for a proof [32].

A closed $\mathrm{\Sigma }$ cuts space into two pieces, a bounded inside piece and an unbounded outside piece. For a point $x\in \mathrm{\Sigma }$, let $n_x$ denote the outside-facing vector normal to $\mathrm{\Sigma }$ at $x$ (and normal to $T_x\mathrm{\Sigma }$). Let $\mathrm{\angle }(n_p,n_q)\in [0^{\circ },{180}^{\circ }]$ denote the angle separating two vectors.

We conclude with homeomorphism theorems for $0.3245$-samples and $0.4132$-Voronoi samples.