University of Maryland, College Park MD,
USAakader@cs.umd.eduhttps://orcid.org/0000-0002-6749-1807University of Texas,
Austin TX, USASupported in part by a contract from Sandia, #1439100, and a
grant from NIH, R01-GM117594 Sandia National Laboratories, Albuquerque NM, USA
University of California, Davis CA, USA Sandia National Laboratories,
Albuquerque NM, USA University of California, Davis CA, USA University of
California, Davis CA, USA Ahmed Abdelkader, Chandrajit L. Bajaj, Mohamed S.
Ebeida, Ahmed H. Mahmoud,
Scott A. Mitchell, John D. Owens and Ahmad A. Rushdi This is an extended
version of the original paper which appeared in the Symposium on Computational
Geometry [1], and includes appendices with proofs that the original paper did
not. See also the accompanying multimedia contribution [2].This material is
based upon work supported by the U.S. Department of Energy, Office of Science,
Office of Advanced Scientific Computing Research (ASCR), Applied Mathematics
Program. Sandia National Laboratories is a multi-mission laboratory managed
and operated by National Technology and Engineering Solutions of Sandia, LLC.,
a wholly owned subsidiary of Honeywell International, Inc., for the U.S.
Department of Energy’s National Nuclear Security Administration under contract
DE-NA0003525. The views expressed in the article do not necessarily represent
the views of the U.S. Department of Energy or the United States Government.

###### Acknowledgements.

We thank Tamal Dey for helpful discussions about surface
reconstruction.Bettina Speckmann and Csaba D. Tóth 2 34th International
Symposium on Computational Geometry (SoCG 2018) SoCG 2018 SoCG 2018 June
11–14, 2018 Budapest, Hungary socg-logo 99 1

# Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust
Algorithm

Ahmed Abdelkader  ,  Chandrajit L. Bajaj  ,  Mohamed S. Ebeida  ,  Ahmed H.
Mahmoud  ,  Scott A. Mitchell  ,  John D. Owens  and  Ahmad A. Rushdi

###### Abstract.

We study the problem of decomposing a volume bounded by a smooth surface into
a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay
meshing, a principled solution to this problem for generic smooth surfaces
remained elusive. VoroCrust leverages ideas from $\alpha$-shapes and the power
crust algorithm to produce unweighted Voronoi cells conforming to the surface,
yielding the first provably-correct algorithm for this problem. Given an
$\epsilon$-sample on the bounding surface, with a weak $\sigma$-sparsity
condition, we work with the balls of radius $\delta$ times the local feature
size centered at each sample. The corners of this union of balls are the
Voronoi sites, on both sides of the surface. The facets common to cells on
opposite sides reconstruct the surface. For appropriate values of $\epsilon$,
$\sigma$ and $\delta$, we prove that the surface reconstruction is isotopic to
the bounding surface. With the surface protected, the enclosed volume can be
further decomposed into an isotopic volume mesh of fat Voronoi cells by
generating a bounded number of sites in its interior. Compared to state-of-
the-art methods based on clipping, VoroCrust cells are full Voronoi cells,
with convexity and fatness guarantees. Compared to the power crust algorithm,
VoroCrust cells are not filtered, are unweighted, and offer greater
flexibility in meshing the enclosed volume by either structured grids or
random samples.

###### Key words and phrases:

sampling conditions, surface reconstruction, polyhedral meshing, Voronoi

###### 1991 Mathematics Subject Classification:

Theory of computation $\rightarrow$ Randomness, geometry and discrete
structures $\rightarrow$ Computational geometry

###### category:

##  1\. Introduction

Mesh generation is a fundamental problem in computational geometry, geometric
modeling, computer graphics, scientific computing and engineering simulations.
There has been a growing interest in polyhedral meshes as an alternative to
tetrahedral or hex-dominant meshes [48]. Polyhedra are less sensitive to
stretching, which enables the representation of complex geometries without
excessive refinement. In addition, polyhedral cells have more neighbors even
at corners and boundaries, which offers better approximations of gradients and
local flow distributions. Even compared to hexahedra, fewer polyhedral cells
are needed to achieve a desired accuracy in certain applications. This can be
very useful in several numerical methods [18], e.g., finite element [42],
finite volume [39], virtual element [17] and Petrov-Galerkin [41]. In
particular, the accuracy of a number of important solvers, e.g., the two-point
flux approximation for conservation laws [39], greatly benefits from a
conforming mesh which is orthogonal to its dual as naturally satisfied by
Voronoi meshes. Such solvers play a crucial role in hydrology [51],
computational fluid dynamics [22] and fracture modeling [20].

VoroCrust is the first provably-correct algorithm for generating a volumetric
Voronoi mesh whose boundary conforms to a smooth bounding surface, and with
quality guarantees. A conforming volume mesh exhibits two desirable properties
_simultaneously_ : (1) a decomposition of the enclosed volume, and (2) a
reconstruction of the bounding surface.

Conforming Delaunay meshing is well-studied [28], but Voronoi meshing is less
mature. A common practical approach to polyhedral meshing is to dualize a
tetrahedral mesh and _clip_ , i.e., intersect and truncate, each cell by the
bounding surface [47, 35, 43, 52, 55]. Unfortunately, clipping sacrifices the
important properties of convexity and connectedness of cells [35], and may
require costly constructive solid geometry operations. Restricting a Voronoi
mesh to the surface before filtering its dual Delaunay facets is another
approach [7, 33, 56], but filtering requires extra checks complicating its
implementation and analysis; see also Figure 4. An intuitive approach is to
locally mirror the Voronoi sites on either side of the surface [57, 34], but
we are not aware of any robust algorithms with approximation guarantees in
this category. In contrast to these approaches, VoroCrust is distinguished by
its simplicity and robustness at producing true unweighted Voronoi cells,
leveraging established libraries, e.g., Voro++ [50], without modification or
special cases.

VoroCrust can be viewed as a principled mirroring technique, which shares a
number of key features with the power crust algorithm [13]. The power crust
literature [8, 7, 10, 12, 13] developed a rich theory for surface
approximation, namely the $\epsilon$-sampling paradigm. Recall that the power
crust algorithm uses an $\epsilon$-sample of unweighted points to place
weighted sites, so-called poles, near the medial axis of the underlying
surface. The surface reconstruction is the collection of facets separating
power cells of poles on the inside and outside of the enclosed volume.

Regarding samples and poles as primal-dual constructs, power crust performs a
_primal-dual-dual-primal dance_. VoroCrust makes a similar dance where weights
are introduced differently; the samples are weighted to define unweighted
sites tightly hugging the surface, with the reconstruction arising from their
unweighted Voronoi diagram. The key advantage is the freedom to place more
sites within the enclosed volume without disrupting the surface
reconstruction. This added freedom is essential to the generation of graded
meshes; a primary virtue of the proposed algorithm. Another virtue of the
algorithm is that all samples appear as vertices in the resulting mesh. While
the power crust algorithm does not guarantee that, some variations do so by
means of filtering, at the price of the reconstruction no longer being the
boundary of power cells [7, 11, 32].

The main construction underlying VoroCrust is a suitable union of balls
centered on the bounding surface, as studied in the context of non-uniform
approximations [26]. Unions of balls enjoy a wealth of results [37, 15, 24],
which enable a variety of algorithms [13, 23, 30].

Similar constructions have been proposed for meshing problems in the applied
sciences with heuristic extensions to 3D settings; see [40] and the references
therein for a recent example. Aichholzer et al. [6] adopt closely related
ideas to construct a union of surface balls using power crust poles for sizing
estimation. However, their goal was to produce a coarse homeomorphic surface
reconstruction. As in [6], the use of balls and $\alpha$-shapes for surface
reconstruction was explored earlier, e.g., ball-pivoting [19, 54], but the
connection to Voronoi meshing has been absent. In contrast, VoroCrust aims at
a decomposition of the enclosed volume into fat Voronoi cells conforming to an
isotopic surface reconstruction with quality guarantees.

In a previous paper [4], we explored the related problem of generating a
Voronoi mesh that conforms to restricted classes of piecewise-linear
complexes, with more challenging inputs left for future work. The approach
adopted in [4] does not use a union of balls and relies instead on similar
ideas to those proposed for conforming Delaunay meshing [45, 29, 49].

In this paper, we present a theoretical analysis of an abstract version of the
VoroCrust algorithm. This establishes the quality and approximation guarantees
of its output for volumes bounded by smooth surfaces. A description of the
algorithm we analyze is given next; see Figure 1 for an illustration in 2D,
and also our accompanying multimedia contribution [2].

### The abstract VoroCrust algorithm

  1. (1)

Take as input a sample $\mathcal{P}$ on the surface $\mathcal{M}$ bounding the
volume $\mathcal{O}$.

  2. (2)

Define a ball $B_{i}$ centered at each sample $p_{i}$, with a suitable radius
$r_{i}$, and let $\mathcal{U}=\cup_{i}B_{i}$.

  3. (3)

Initialize the set of sites $\mathcal{S}$ with the corner points of
$\partial\mathcal{U}$, $\mathcal{S}^{\uparrow}$ and
$\mathcal{S}^{\downarrow}$, on both sides of $\mathcal{M}$.

  4. (4)

Optionally, generate additional sites $\mathcal{S}^{\downarrow\downarrow}$ in
the interior of $\mathcal{O}$, and include
$\mathcal{S}^{\downarrow\downarrow}$ into $\mathcal{S}$.

  5. (5)

Compute the Voronoi diagram $\textrm{Vor}(\mathcal{S})$ and retain the cells
with sites in $\mathcal{S}^{\downarrow}\cup\mathcal{S}^{\downarrow\downarrow}$
as the volume mesh $\hat{\mathcal{O}}$, where the facets between
$\mathcal{S}^{\uparrow}$ and $\mathcal{S}^{\downarrow}$ yield a surface
approximation $\hat{\mathcal{M}}$.

(a) Surface balls.

(b) Labeled corners.

(c) Voronoi cells.

(d) Reconstruction.

Figure 1. VoroCrust reconstruction, demonstrated on a planar curve.

In this paper, we assume $\mathcal{O}$ is a bounded open subset of
$\mathbb{R}^{3}$, whose boundary $\mathcal{M}$ is a closed, bounded and smooth
surface. We further assume that $\mathcal{P}$ is an $\epsilon$-sample, with a
weak $\sigma$-sparsity condition, and $r_{i}$ is set to $\delta$ times the
local feature size at $p_{i}$. For appropriate values of $\epsilon$, $\sigma$
and $\delta$, we prove that $\hat{\mathcal{O}}$ and $\hat{\mathcal{M}}$ are
isotopic to $\mathcal{O}$ and $\mathcal{M}$, respectively. We also show that
simple techniques for sampling within $\mathcal{O}$, e.g., octree refinement,
guarantee an upper bound on the fatness of all cells in $\hat{\mathcal{O}}$,
as well as the number of samples.

Ultimately, we seek a conforming Voronoi mesher that can handle realistic
inputs possibly containing sharp features, can estimate a sizing function and
generate samples, and can guarantee the quality of the output mesh. This is
the subject of a forthcoming paper [3] which describes the design and
implementation of the complete VoroCrust algorithm.

The rest of the paper is organized as follows. Section 2 introduces the key
definitions and notation used throughout the paper. Section 3 describes the
placement of Voronoi seeds and basic properties of our construction assuming
the union of surface balls satisfies a structural property. Section 4 proves
this property holds and establishes the desired approximation guarantees under
certain conditions on the input sample. Section 5 considers the generation of
interior samples and bounds the fatness of all cells in the output mesh.
Section 6 concludes the paper with pointers for future work. A number of
proofs are deferred to the appendices; see also the accompanying multimedia
contribution [2].

##  2\. Preliminaries

Throughout, standard general position assumptions [38] are made implicitly to
simplify the presentation. We use $\textbf{d}(p,q)$ to denote the Euclidean
distance between two points $p,q\in\mathbb{R}^{3}$, and $\mathbb{B}(c,r)$ to
denote the Euclidean ball centered at $c\in\mathbb{R}^{3}$ with radius $r$. We
proceed to introduce the notation and recall the key definitions used
throughout, following those in [37, 13, 26].

###  2.1. Sampling and approximation

We take as input a set of sample points $\mathcal{P}\subset\mathcal{M}$. A
local scale or sizing is used to vary the sample density. Recall that the
medial axis [13] of $\mathcal{M}$, denoted by $\mathcal{A}$, is the closure of
the set of points in $\mathbb{R}^{3}$ with more than one closest point on
$\mathcal{M}$. Hence, $\mathcal{A}$ has one component inside $\mathcal{O}$ and
another outside. Each point of $\mathcal{A}$ is the center of a medial ball
tangent to $\mathcal{M}$ at multiple points. Likewise, each point on
$\mathcal{M}$ has two tangent medial balls, not necessarily of the same size.
The local feature size at $x\in\mathcal{M}$ is defined as
$\textrm{lfs}(x)=\inf_{{a\in\mathcal{A}}}\textbf{d}(x,a)$. The set
$\mathcal{P}$ is an $\epsilon$-sample [9] if for all $x\in\mathcal{M}$ there
exists $p\in\mathcal{P}$ such that
$\textbf{d}(x,p)\leq\epsilon\cdot\textrm{lfs}(x)$.

We desire an approximation of $\mathcal{O}$ by a Voronoi mesh
$\hat{\mathcal{O}}$, where the boundary $\hat{\mathcal{M}}$ of
$\hat{\mathcal{O}}$ approximates $\mathcal{M}$. Recall that two topological
spaces are homotopy-equivalent [26] if they have the same topology type. A
stronger notion of topological equivalence is homeomorphism, which holds when
there exists a continuous bijection with a continuous inverse from
$\mathcal{M}$ to $\hat{\mathcal{M}}$. The notion of isotopy captures an even
stronger type of equivalence for surfaces embedded in Euclidean space. Two
surfaces $\mathcal{M},\hat{\mathcal{M}}\subset\mathbb{R}^{3}$ are isotopic
[16, 25] if there is a continuous mapping
$F:\mathcal{M}\times[0,1]\to\mathbb{R}^{3}$ such that for each $t\in[0,1]$,
$F(\cdot,t)$ is a homeomorphism from $\mathcal{M}$ to $\hat{\mathcal{M}}$,
where $F(\cdot,0)$ is the identity of $\mathcal{M}$ and
$F(\mathcal{M},1)=\hat{\mathcal{M}}$. To establish that two surfaces are
geometrically close, the distance between each point on one surface and its
closest point on the other surface is required. Such a bound is usually
obtained in the course of proving isotopy.

###  2.2. Diagrams and triangulations

The set of points defining a Voronoi diagram are traditionally referred to as
sites or seeds. When approximating a manifold by a set of sample points of
varying density, it is helpful to assign weights to the points reflective of
their density. In particular, a point $p_{i}$ with weight $w_{i}$, can be
regarded as a ball $B_{i}$ with center $p_{i}$ and radius
$r_{i}=\sqrt{w_{i}}$.

Recall that the power distance [37] between two points $p_{i},p_{j}$ with
weights $w_{i},w_{j}$ is
$\pi(p_{i},p_{j})=\textbf{d}(p_{i},p_{j})^{2}-w_{i}-w_{j}$. Unless otherwise
noted, points are unweighted, having weight equal to zero. There is a natural
geometric interpretation of the weight: all points $q$ on the boundary of
$B_{i}$ have $\pi(p_{i},q)=0$, inside $\pi(p_{i},q)<0$ and outside
$\pi(p_{i},q)>0.$ Given a set of weighted points $\mathcal{P}$, this metric
gives rise to a natural decomposition of $\mathbb{R}^{3}$ into the power cells
$V_{i}=\\{q\in\mathbb{R}^{3}\mid\pi(p_{i},q)\leq\pi(p_{j},q)\>\forall
p_{j}\in\mathcal{P}\\}$. The power diagram $\textrm{wVor}(\mathcal{P})$ is the
cell complex defined by collection of cells $V_{i}$ for all
$p_{i}\in\mathcal{P}$.

The nerve [37] of a collection $\mathcal{C}$ of sets is defined as
$\mathcal{N}(\mathcal{C})=\\{X\subseteq\mathcal{C}\mid\cap\>T\neq\emptyset\\}$.
Observe that $\mathcal{N}(\mathcal{C})$ is an abstract simplicial complex
because $X\in\mathcal{N}(\mathcal{C})$ and $Y\subseteq X$ imply
$Y\in\mathcal{N}(\mathcal{C})$. With that, we obtain the weighted Delaunay
triangulation, or regular triangulation, as
$\textrm{wDel}(\mathcal{P})=\mathcal{N}(\textrm{wVor}(\mathcal{P}))$.
Alternatively, $\textrm{wDel}(\mathcal{P})$ can be defined directly as
follows. A subset $T\subset\mathbb{R}^{d}$, with $d\leq 3$ and $|T|\leq d+1$
defines a $d$-simplex $\sigma_{T}$. Recall that the orthocenter [27] of
$\sigma_{T}$, denoted by $z_{T}$, is the unique point $q\in\mathbb{R}^{d}$
such that $\pi(p_{i},z_{T})=\pi(p_{j},z_{T})$ for all $p_{i},p_{j}\in T$; the
orthoradius of $\sigma_{T}$ is equal to $\pi(p,z_{T})$ for any $p\in T$. The
Delaunay condition defines $\textrm{wDel}(\mathcal{P})$ as the set of
tetrahedra $\sigma_{T}$ with an empty orthosphere, meaning
$\pi(p_{i},z_{T})\leq\pi(p_{j},z_{T})$ for all $p_{i}\in T$ and
$p_{j}\in\mathcal{P}\setminus T$, where $\textrm{wDel}(\mathcal{P})$ includes
all faces of $\sigma_{T}$.

There is a natural duality between $\textrm{wDel}(\mathcal{P})$ and
$\textrm{wVor}(\mathcal{P})$. For a tetrahedron $\sigma_{T}$, the definition
of $z_{T}$ immediately implies $z_{T}$ is a power vertex in
$\textrm{wVor}(\mathcal{P})$. Similarly, for each $k$-face $\sigma_{S}$ of
$\sigma_{T}\in\textrm{wDel}(\mathcal{P})$ with $S\subseteq T$ and $k+1=|S|$,
there exists a dual $(3-k)$-face $\sigma^{\prime}_{S}$ in
$\textrm{wVor}(\mathcal{P})$ realized as $\cap_{p\in S}V_{p}$. When
$\mathcal{P}$ is unweighted, the same definitions yield the standard
(unweighted) Voronoi diagram $\textrm{Vor}(\mathcal{P})$ and its dual Delaunay
triangulation $\textrm{Del}(\mathcal{P})$.

###  2.3. Unions of balls

Let $\mathcal{B}$ denote the set of balls corresponding to a set of weighted
points $\mathcal{P}$ and define the union of balls $\mathcal{U}$ as
$\cup\mathcal{B}$. It is quite useful to capture the structure of
$\mathcal{U}$ using a combinatorial representation like a simplicial complex
[37, 36]. Let $f_{i}$ denote $V_{i}\cap\partial B_{i}$ and $\mathcal{F}$ the
collection of all such $f_{i}$. Observing that $V_{i}\cap B_{j}\subseteq
V_{i}\cap B_{i}\>\forall B_{i},B_{j}\in\mathcal{B}$, $f_{i}$ is equivalently
defined as the spherical part of $\partial(V_{i}\cap B_{i})$. Consider also
the decomposition of $\mathcal{U}$ by the cells of
$\textrm{wVor}(\mathcal{P})$ into $\mathcal{C}(\mathcal{B})=\\{V_{i}\cap
B_{i}\mid B_{i}\in\mathcal{B}\\}$. The weighted $\alpha$-complex
$\mathcal{W}(\mathcal{P})$ is defined as the geometric realization of
$\mathcal{N}(\mathcal{C}(\mathcal{B}))$ [37], i.e., $\sigma_{T}\in\mathcal{W}$
if $\\{V_{i}\cap B_{i}\mid p_{i}\in
T\\}\in\mathcal{N}(\mathcal{C}(\mathcal{B}))$. It is not hard to see that
$\mathcal{W}$ is a subcomplex of $\textrm{wDel}(\mathcal{P})$.

To see why $\mathcal{W}$ is relevant, consider its underlying space; we create
a collection containing the convex hull of each simplex in $\mathcal{W}$ and
define the weighted $\alpha$-shape $\mathcal{J}(\mathcal{P})$ as the union of
this collection. It turns out that the simplices $\sigma_{T}\in\mathcal{W}$
contained in $\partial\mathcal{J}$ are dual to the faces of
$\partial\mathcal{U}$ defined as $\cap_{i\in T}f_{i}$. Every point
$q\in\partial\mathcal{U}$ defined by $\cap_{i\in T_{q}}f_{i}$, for
$T_{q}\in\mathcal{B}$ and $k+1=|T_{q}|$, witnesses the existence of
$\sigma_{T_{q}}$ in $\mathcal{W}$; the $k$-simplex $\sigma_{T_{q}}$ is said to
be exposed and $\partial\mathcal{J}$ can be defined directly as the collection
of all exposed simplices [36]. In particular, the corners of
$\partial\mathcal{U}$ correspond to the facets of $\partial\mathcal{J}$.
Moreover, $\mathcal{J}$ is homotopy-equivalent to $\mathcal{U}$ [37].

The union of balls defined using an $\epsilon$-sampling guarantees the
approximation of the manifold under suitable conditions on the sampling.
Following earlier results on uniform sampling [46], an extension to non-
uniform sampling establishes sampling conditions for the isotopic
approximation of hypersurfaces and medial axis reconstruction [26].

##  3\. Seed placement and surface reconstruction

We determine the location of Voronoi seeds using the union of balls
$\mathcal{U}$. The correctness of our reconstruction depends crucially on how
sample balls $\mathcal{B}$ overlap. Assuming a certain structural property on
$\mathcal{U}$, the surface reconstruction is embedded in the dual shape
$\mathcal{J}$.

###  3.1. Seeds and guides

Central to the method and analysis are triplets of sample spheres, i.e.,
boundaries of sample balls, corresponding to a _guide triangle_ in
$\textrm{wDel}(\mathcal{P})$. The sample spheres associated with the vertices
of a guide triangle intersect contributing a pair of _guide points_. The
reconstruction consists of Voronoi facets, most of which are guide triangles.

(a) Overlapping balls and guide circles.

(b) Pattern resulting in four half-covered seed pairs.

Figure 2. (a) Guide triangle and its dual seed pair. (b) Cutaway view in the
plane of circle $C_{34}$.

When a triplet of spheres $\partial B_{i},\partial B_{j},\partial B_{k}$
intersect at exactly two points, the intersection points are denoted by
${g^{\updownarrow}_{ijk}}=\\{{g^{\uparrow}_{ijk}},{g^{\downarrow}_{ijk}}\\}$
and called a pair of _guide points_ or _guides_ ; see Figure 2(a). The
associated guide triangle $t_{ijk}$ is _dual_ to ${g^{\updownarrow}_{ijk}}$.
We use arrows to distinguish guides on different sides of the manifold with
the upper guide ${g^{\uparrow}}$ lying outside $\mathcal{O}$ and the lower
guide ${g^{\downarrow}}$ lying inside. We refer to the edges of guide
triangles as _guide edges_ $e_{ij}=\overline{p_{i}p_{j}}$. A guide edge
$e_{ij}$ is associated with a dual _guide circle_ $C_{ij}=\partial
B_{i}\cap\partial B_{j}$, as in Figure 2(a).

The Voronoi seeds in $\mathcal{S}^{\uparrow}\cup\mathcal{S}^{\downarrow}$ are
chosen as the subset of guide points that lie on $\partial\mathcal{U}$. A
guide point $g$ which is not interior to any sample ball is _uncovered_ and
included as a _seed_ $s$ into $\mathcal{S}$; covered guides are not. We denote
_uncovered guides_ by $s$ and _covered guides_ by $g$, whenever coverage is
known and important. If only one guide point in a pair is covered, then we say
the guide pair is _half-covered_. If both guides in a pair are covered, they
are ignored. Let $\mathcal{S}_{i}=\mathcal{S}\cap\partial B_{i}$ denote the
seeds on sample sphere $\partial B_{i}$.

As each guide triangle $t_{ijk}$ is associated with at least one dual seed
$s_{ijk}$, the seed witnesses its inclusion in $\mathcal{W}$ and $t_{ijk}$ is
exposed. Hence, $t_{ijk}$ belongs to $\partial\mathcal{J}$ as well. When such
$t_{ijk}$ is dual to a single seeds $s_{ijk}$ it bounds the interior of
$\mathcal{J}$, i.e., it is a face of a regular component of $\mathcal{J}$; in
the simplest and most common case, $t_{ijk}$ is a facet of a tetrahedron as
shown in Figure 3(b). When $t_{ijk}$ is dual to a pair of seeds
${s^{\updownarrow}_{ijk}}$, it does not bound the interior of $\mathcal{J}$
and is called a singular face of $\partial\mathcal{J}$. All singular faces of
$\partial\mathcal{J}$ appear in the reconstructed surface.

###  3.2. Disk caps

We describe the structural property required on $\mathcal{U}$ along with the
consequences exploited by VoroCrust for surface reconstruction. This is
partially motivated by the requirement that all sample points on the surface
appear as vertices in the output Voronoi mesh.

We define the subset of $\partial B_{i}$ inside other balls as the _medial
band_ and say it is _covered_. Let the caps $K^{\uparrow}_{i}$ and
$K^{\downarrow}_{i}$ be the complement of the medial band in the interior and
exterior of $\mathcal{O}$, respectively. Letting $n_{p_{i}}$ be the normal
line through $p_{i}$ perpendicular to $\mathcal{M}$, the two intersection
points $n_{p_{i}}\cap\partial B_{i}$ are called the _poles_ of $B_{i}$. See
Figure 3(a).

(a) Caps and medial band.

(b) Sliver and half-covered seeds, exaggerated vertical scale.

Figure 3. (a) Decomposing the sample sphere $\partial B_{1}$. (b) Uncovered
seeds and reconstruction facets. Let
$\tau_{p}\in\mathcal{W}(\mathcal{P})\subseteq\textrm{wDel}(\mathcal{P})$ and
$\tau_{s}\in\textrm{Del}(\mathcal{S})$ denote the tetrahedra connecting the
four samples and the four seeds shown, respectively. ${s^{\downarrow}_{123}}$
and ${s^{\downarrow}_{134}}$ are the uncovered lower guide seeds, with
${g^{\uparrow}_{123}}$ and ${g^{\uparrow}_{134}}$ covered. The uncovered upper
guide seeds are ${s^{\uparrow}_{124}}$ and ${s^{\uparrow}_{234}}$, with
${g^{\downarrow}_{124}}$ and ${g^{\downarrow}_{234}}$ covered.
$\triangle_{ac}$ is the Voronoi facet dual to the Delaunay edge between
${}^{a}{s^{\downarrow}_{123}}$ and ${}^{c}{s^{\uparrow}_{124}}$, etc. Voronoi
facets dual to magenta edges are in the reconstructed surface; those dual to
green and blue edges are not. $n$ is the circumcenter of $\tau_{s}$ and
appears as a Voronoi vertex in $\textrm{Vor}(\mathcal{S})$ and a Steiner
vertex in the surface reconstruction. In general, $n$ is not the orthocenter
of the sliver $\tau_{p}$.

We require that $\mathcal{U}$ satisfies the following structural property:
each $\partial B_{i}$ has _disk caps_ , meaning the medial band is a
topological annulus and the two caps contain the poles and are topological
disks. In other words, each $B_{i}$ contributes one connected component to
each side of $\partial\mathcal{U}$. As shown in Figure 3(a), all seeds in
$\mathcal{S}^{\uparrow}_{i}$ and $\mathcal{S}^{\downarrow}_{i}$ lie on
$\partial K^{\uparrow}_{i}$ and $\partial K^{\downarrow}_{i}$, respectively,
along the arcs where other sample balls intersect $\partial B_{i}$. In Section
4, we establish sufficient sampling conditions to ensure $\mathcal{U}$
satisfies this property. In particular, we will show that both poles of each
$B_{i}$ lie on $\partial\mathcal{U}$.

The importance of disk caps is made clear by the following observation. The
requirement that all sample points appear as Voronoi vertices in
$\hat{\mathcal{M}}$ follows as a corollary.

######  Observation  (Three upper/lower seeds).

If $\partial B_{i}$ has _disk caps_ , then each of $\partial K^{\uparrow}_{i}$
and $\partial K^{\downarrow}_{i}$ has at least three seeds and the seeds on
$\partial B_{i}$ are not all coplanar.

###### Proof.

Every sphere $S_{j\neq i}$ covers strictly less than one hemisphere of
$\partial B_{i}$ because the poles are uncovered. Hence, each cap is composed
of at least three arcs connecting at least three upper seeds
$\mathcal{S}^{\uparrow}_{i}\subset\partial K^{\uparrow}_{i}$ and three lower
seeds $\mathcal{S}^{\downarrow}_{i}\subset\partial K^{\downarrow}_{i}$.
Further, any hemisphere through the poles contains at least one upper and one
lower seed. It follows that the set of seeds
$\mathcal{S}_{i}=\mathcal{S}_{i}^{\uparrow}\cup\mathcal{S}_{i}^{\downarrow}$
is not coplanar. ∎

######  Corollary  (Sample reconstruction).

If $\partial B_{i}$ has disk caps, then $p_{i}$ is a vertex in
$\hat{\mathcal{M}}$.

###### Proof.

By Section 3.2, the sample is equidistant to at least four seeds which are not
all coplanar. It follows that the sample appears as a vertex in the Voronoi
diagram and not in the relative interior of a facet or an edge. Being a common
vertex to at least one interior and one exterior Voronoi seed, VoroCrust
retains this vertex in its output reconstruction. ∎

###  3.3. Sandwiching the reconstruction in the dual shape of $\mathcal{U}$

Triangulations of smooth surfaces embedded in $\mathbb{R}^{3}$ can have half-
covered guides pairs, with one guide covered by the ball of a fourth sample
not in the guide triangle dual to the guide pair. The tetrahedron formed by
the three samples of the guide triangle plus the fourth covering sample is a
_sliver_ , i.e., the four samples lie almost uniformly around the equator of a
sphere. In this case we do not reconstruct the guide triangle, and also do not
reconstruct some guide edges. We show that the reconstructed surface
$\hat{\mathcal{M}}$ lies entirely within the region of space bounded by guide
triangles, i.e., the $\alpha$-shape of $\mathcal{P}$, as stated in the
following theorem.

######  Theorem 3.1.

If all sample balls have disk caps, then
$\hat{\mathcal{M}}\subseteq\mathcal{J}(\mathcal{P})$.

Figure 4. Cutaway view of a sliver tetrahedron
$\tau_{p}\in\mathcal{W}(\mathcal{P})\subseteq\textrm{wDel}(\mathcal{P})$,
drawn to scale. Half-covered guides give rise to the Steiner vertex (pink),
which results in a surface reconstruction using four facets (only two are
shown) sandwiched within $\tau_{p}$. In contrast, filtering
$\textrm{wDel}(\mathcal{P})$ chooses two of the four facets of $\tau_{p}$,
either the bottom two, or the top two (only one is shown).

The simple case of a single isolated sliver tetrahedron is illustrated in
Figures 3(b), 4 and 2(b). A sliver has a pair of lower guide triangles and a
pair of upper guide triangles. For instance, $t_{124}$ and $t_{234}$ are the
pair of upper triangles in Figure 3(b). In such a tetrahedron, there is an
edge between each pair of samples corresponding to a non-empty circle of
intersection between sample balls, like the circles in Figure 2(a). For this
circle, the arcs covered by the two other sample balls of the sliver overlap,
so each of these balls contributes exactly one uncovered seed, rather than
two. In this way the upper guides for the upper triangles are uncovered, but
their lower guides are covered; also only the lower guides of the lower
triangles are uncovered. The proof of Theorem 3.1 follows by analyzing the
Voronoi cells of the seed points located on the overlapping sample balls and
is deferred to Appendix A. Alternatively, Theorem 3.1 can be seen as a
consequence of Theorem 2 in [15].

##  4\. Sampling conditions and approximation guarantees

We take as input a set of points $\mathcal{P}$ sampled from the bounding
surface $\mathcal{M}$ such that $\mathcal{P}$ is an $\epsilon$-sample, with
$\epsilon\leq 1/500$. We require that $\mathcal{P}$ satisfies the following
sparsity condition: for any two points $p_{i},p_{j}\in P$,
$\textrm{lfs}(p_{i})\geq\textrm{lfs}(p_{j})\implies\textbf{d}(p_{i},p_{j})\geq\sigma\epsilon\textrm{lfs}(p_{j})$,
with $\sigma\geq 3/4$.

Such a sampling $\mathcal{P}$ can be obtained by known algorithms. Given a
suitable representation of $\mathcal{M}$, the algorithm in [21] computes a
loose $\epsilon^{\prime}$-sample $E$ which is a
$\epsilon^{\prime}(1+8.5\epsilon^{\prime})$-sample. More specifically,
whenever the algorithm inserts a new sample $p$ into the set $E$,
$\textbf{d}(p,E)\geq\epsilon^{\prime}\textrm{lfs}(p)$. To obtain $E$ as an
$\epsilon$-sample, we set
$\epsilon^{\prime}(\epsilon)=(\sqrt{34\epsilon+1}-1)/17$. Observing that
$3\epsilon/4\leq\epsilon^{\prime}(\epsilon)$ for $\epsilon\leq 1/500$, the
returned $\epsilon$-sample satisfies our required sparsity condition with
$\sigma\geq 3/4$.

We start by adapting Theorem 6.2 and Lemma 6.4 from [26] to the setting just
described. For $x\in\mathbb{R}^{3}\setminus M$, let
$\Gamma(x)=\textbf{d}(x,\tilde{x})/\textrm{lfs}(\tilde{x})$, where $\tilde{x}$
is the closest point to $x$ on $\mathcal{M}$.

######  Corollary 4.1.

For an $\epsilon$-sample $\mathcal{P}$, with $\epsilon\leq 1/20$, the union of
balls $\mathcal{U}$ with $\delta=2\epsilon$ satisfies:

  1. (1)

$\mathcal{M}$ is a deformation retract of $\mathcal{U}$,

  2. (2)

$\partial\mathcal{U}$ contains two connected components, each isotopic to
$\mathcal{M}$,

  3. (3)

$\Gamma^{-1}([0,a^{\prime}])\subset U\subset\Gamma^{-1}([0,b^{\prime}])$,
where $a^{\prime}=\epsilon-2\epsilon^{2}$ and $b^{\prime}\leq 2.5\epsilon$.

######  Proof 4.2.

Theorem 6.2 from [26] is stated for balls with radii within $[a,b]$ times the
lfs. We set $a=b=\delta$ and use $\epsilon\leq 1/20$ to simplify fractions.
This yields the above expressions for $a^{\prime}=(1-\epsilon)\delta-\epsilon$
and $b^{\prime}=\delta/(1-2\delta)$. The general condition requires
$(1-a^{\prime})^{2}+\big{(}b^{\prime}-a^{\prime}+\delta(1+2b^{\prime}-a^{\prime})/(1-\delta)\big{)}^{2}<1$,
as we assume no noise. Plugging in the values of $a^{\prime}$ and
$b^{\prime}$, we verify that the inequality holds for the chosen range of
$\epsilon$.

Furthermore, we require that each ball $B_{i}\in\mathcal{B}$ contributes one
facet to each side of $\partial\mathcal{U}$. Our sampling conditions ensure
that both poles are outside any ball $B_{j}\in\mathcal{B}$.

######  Lemma 4.3 (Disk caps).

All balls in $\mathcal{B}$ have disk caps for $\epsilon\leq 0.066$,
$\delta=2\epsilon$ and $\sigma\geq 3/2$.

######  Proof 4.4.

Fix a sample $p_{i}$ and let $x$ be one of the poles of $B_{i}$ and
$B_{x}=\mathbb{B}(c,\textrm{lfs}(p_{i}))$ the tangent ball at $p_{i}$ with
$x\in B_{x}$. Letting $p_{j}$ be the closest sample to $x$ in
$P\setminus\\{p_{i}\\}$, we assume the worst case where
$\textrm{lfs}(p_{j})\geq\textrm{lfs}(p_{i})$ and $p_{j}$ lies on $\partial
B_{x}$. To simplify the calculations, take $\textrm{lfs}(p_{i})=1$ and let
$\ell$ denote $\textbf{d}(p_{i},p_{j})$. As lfs is 1-Lipschitz, we get
$\textrm{lfs}(p_{j})\leq 1+\ell$. By the law of cosines,
$\textbf{d}(p_{j},x)^{2}=\textbf{d}(p_{i},p_{j})^{2}+\textbf{d}(p_{i},x)^{2}-2\textbf{d}(p_{i},p_{j})\textbf{d}(p_{i},x)\cos(\phi)$,
where $\phi=\angle p_{j}p_{i}c$. Letting $\theta=\angle p_{i}cp_{j}$, observe
that $\cos(\phi)=\sin(\theta/2)=\ell/2$. To enforce $x\notin B_{j}$, we
require $\textbf{d}(p_{j},x)>\delta\textrm{lfs}(p_{j})$, which is equivalent
to $\ell^{2}+\delta^{2}-\delta\ell^{2}>\delta^{2}(1+\ell)^{2}$. Simplifying,
we get $\ell>2\delta^{2}/(1-\delta-\delta^{2})$ where sparsity guarantees
$\ell>\sigma\epsilon$. Setting
$\sigma\epsilon>2\delta^{2}/(1-\delta-\delta^{2})$ we obtain
$4\sigma\epsilon^{2}+(8+2\sigma)\epsilon-\sigma<0$, which requires
$\epsilon<0.066$ when $\sigma\geq 3/4$.

4.1 together with 4.3 imply that each $\partial B_{i}$ is decomposed into a
covered region $\partial B_{i}\cap\cup_{j\neq i}B_{j}$, the _medial band_ ,
and two uncovered caps $\partial B_{i}\setminus\cup_{j\neq i}B_{j}$, each
containing one pole. Recalling that seeds arise as pairs of intersection
points between the boundaries of such balls, we show that seeds can be
classified correctly as either inside or outside $\mathcal{M}$.

######  Corollary 4.5.

If a seed pair lies on the same side of $\mathcal{M}$, then at least one seed
is covered.

######  Proof 4.6.

Fix such a seed pair $\partial B_{i}\cap\partial B_{j}\cap\partial B_{k}$ and
recall that $\mathcal{M}\cap\partial B_{i}$ is contained in the medial band on
$\partial B_{i}$. Now, assume for contradiction that both seeds are uncovered
and lie on the same side of $\mathcal{M}$. It follows that $B_{j}\cap B_{k}$
intersects $B_{i}$ away from its medial band, a contradiction to 4.1.

4.1 guarantees that the medial band of $B_{i}$ is a superset of
$\Gamma^{-1}([0,a^{\prime}])\cap\partial B_{i}$, which means that all seeds
$s_{ijk}$ are at least $a^{\prime}\textrm{lfs}(\tilde{s}_{ijk})$ away from
$\mathcal{M}$. It will be useful to bound the elevation of such seeds above
$T_{p_{i}}$, the tangent plane to $\mathcal{M}$ at $p_{i}$.

######  Lemma 4.7.

For a seed $s\in\partial B_{i}$, $\theta_{s}=\angle sp_{i}s^{\prime}\geq
29.34^{\circ}$ and $\theta_{s}>\frac{1}{2}-5\epsilon$, where $s^{\prime}$ is
the projection of $s$ on $T_{p_{i}}$, implying $\textbf{d}(s,s^{\prime})\geq
h^{\bot}_{s}\delta\textrm{lfs}(p_{i})$, with $h^{\bot}_{s}>0.46$ and
$h^{\bot}_{s}>\frac{1}{2}-5\epsilon$.

######  Proof 4.8.

Let $\textrm{lfs}(p_{i})=1$ and $B_{s}=\mathbb{B}(c,1)$ be the tangent ball at
$p_{i}$ with $s\notin B_{s}$; see Figure 5(a). Observe that
$\textbf{d}(s,\mathcal{M})\leq\textbf{d}(s,x)$, where
$x=\overline{sc}\cap\partial B_{s}$. By the law of cosines,
$\textbf{d}(s,c)^{2}=\textbf{d}(p_{i},c)^{2}+\textbf{d}(p_{i},s)^{2}-2\textbf{d}(p_{i},c)\textbf{d}(p_{i},s)\cos(\pi/2+\theta_{s})=1+\delta^{2}+2\delta\sin(\theta_{s})$.
We may write111Define $f(u,v)=\sqrt{1+u^{2}+2uv}-(1+u^{2}/2+uv)$ and observe
that $f(u,-u/2)=0$ is the only critical value of $f(u,.)$. As
$\partial^{2}f/\partial v^{2}\leq 0$ for $(u,v)\in\mathbb{R}\times[-1,1]$, we
get that $f(u,v)\leq 0$ in this range. $\textbf{d}(s,c)\leq
1+\delta^{2}/2+\delta\sin(\theta_{s})$. It follows that
$\textbf{d}(s,x)\leq\delta^{2}/2+\delta\sin(\theta_{s})$. As lfs is
1-Lipschitz and $\textbf{d}(p_{i},x)\leq\delta$, we get
$1-\delta\leq\textrm{lfs}(x)\leq 1+\delta$. There must exist a sample $p_{j}$
such that
$\textbf{d}(x,p_{j})\leq\epsilon\textrm{lfs}(x)\leq\epsilon(1+\delta)$.
Similarly, $\textrm{lfs}(p_{j})\geq(1-\epsilon(1+\delta))(1-\delta)$. By the
triangle inequality,
$\textbf{d}(s,p_{j})\leq\textbf{d}(s,x)+\textbf{d}(x,p_{j})\leq\delta^{2}/2+\delta\sin(\theta_{s})+\epsilon(1+\delta)$.
Setting $\textbf{d}(s,p_{j})<\delta(1-\delta)(1-\epsilon(1+\delta))$ implies
$\textbf{d}(s,p_{j})<\delta\textrm{lfs}(p_{j})$, which shows that for small
values of $\theta_{s}$, $s$ cannot be a seed and $p_{j}\neq p_{i}$.
Substituting $\delta=2\epsilon$, we get
$\theta_{s}\geq\sin^{-1}{(2\epsilon^{3}-5\epsilon+1/2)}\geq 29.34^{\circ}$ and
$\theta_{s}>1/2-5\epsilon$.

We make frequent use of the following bound on the distance between related
samples.

######  Claim 4.9.

If $B_{i}\cap B_{j}\neq\emptyset$, then
$\textbf{d}(p_{i},p_{j})\in[\kappa_{\epsilon},\kappa\delta]\cdot\textrm{lfs}(p_{i})$,
with $\kappa=2/(1-\delta)$ and
$\kappa_{\epsilon}=\sigma\epsilon/(1+\sigma\epsilon)$.

######  Proof 4.10.

The upper bound comes from $\textbf{d}(p_{i},p_{j})\leq r_{i}+r_{j}$ and
$\textrm{lfs}(p_{j})\leq\textrm{lfs}(p_{i})+\textbf{d}(p_{i},d_{j})$ by
1-Lipschitz, and the lower bound from
$\textrm{lfs}(p_{i})-\textbf{d}(p_{i},d_{j})\leq\textrm{lfs}(p_{j})$ and the
sparsity.

Bounding the circumradii is the culprit behind why we need such small values
of $\epsilon$.

######  Lemma 4.11.

The circumradius of a guide triangle $t_{ijk}$ is at most
$\varrho_{f}\cdot\delta\textrm{lfs}(p_{i})$, where $\varrho_{f}<1.38$, and at
most $\overline{\varrho}_{f}\cdot\textbf{d}(p_{i},p_{j})$ where
$\overline{\varrho}_{f}<3.68$.

######  Proof 4.12.

Let $p_{i}$ and $p_{j}$ be the triangle vertices with the smallest and largest
lfs values, respectively. From 4.9, we get
$\textbf{d}(p_{i},p_{j})\leq\kappa\delta\textrm{lfs}(p_{i})$. It follows that
$\textrm{lfs}(p_{j})\leq(1+\kappa\delta)\textrm{lfs}(p_{i})$. As $t_{ijk}$ is
a guide triangle, we know that it has a pair of intersection points $\partial
B_{i}\cap\partial B_{j}\cap\partial B_{k}$. Clearly, the seed is no farther
than $\delta\textrm{lfs}(p_{j})$ from any vertex of $t_{ijk}$ and the
orthoradius of $t_{ijk}$ cannot be bigger than this distance.

Recall that the weight $w_{i}$ associated with $p_{i}$ is
$\delta^{2}\textrm{lfs}(p_{i})^{2}$. We shift the weights of all the vertices
of $t_{ijk}$ by the lowest weight $w_{i}$, which does not change the
orthocenter. With that
$w_{j}-w_{i}=\delta^{2}(\textrm{lfs}(p_{j})^{2}-\textrm{lfs}(p_{i})^{2})\leq\delta^{2}\textrm{lfs}(p_{i})^{2}((1+\kappa\delta)^{2}-1)=\kappa\delta^{3}\textrm{lfs}(p_{i})^{2}(\kappa\delta+2)$.
On the other hand, sparsity ensures that the closest vertex in $t_{ijk}$ to
$p_{j}$ is at distance at least
$N(p_{j})\geq\sigma\epsilon\textrm{lfs}(p_{j})\geq\sigma\epsilon(1-\kappa\delta)\textrm{lfs}(p_{i})$.
Ensuring
$\alpha^{2}\leq(w_{j}-w_{i})/N(p_{i})^{2}\leq\kappa\delta^{3}(2+\kappa\delta)/(\sigma^{2}\epsilon^{2}(1-\kappa\delta)^{2})\leq
1/4$ suffices to bound the circumradius of $t_{ijk}$ by
$c_{rad}=1/\sqrt{1-4\alpha^{2}}$ times its orthoradius, as required by Claim 4
in [27]. Substituting $\delta=2\epsilon$ and $\sigma\geq 3/4$ we get
$\alpha^{2}\leq 78.97\epsilon$, which corresponds to $c_{rad}<1.37$. It
follows that the circumradius is at most $c_{rad}\delta\textrm{lfs}(p_{j})\leq
c_{rad}(1+\kappa\delta)\delta\textrm{lfs}(p_{i})<1.38\delta\textrm{lfs}(p_{i})$.

For the second statement, observe that
$\textrm{lfs}(p_{i})\geq(1-\kappa\delta)\textrm{lfs}(p_{j})$ and the sparsity
condition ensures that the shortest edge length is at least
$\sigma\epsilon\textrm{lfs}(p_{i})\geq\sigma\epsilon(1-\kappa\delta)\textrm{lfs}(p_{j})$.
It follows that the circumradius is at most $\frac{\delta
c_{rad}}{\sigma\epsilon(1-\kappa\delta)}<3.68$ times the length of any edge of
$t_{ijk}$.

Given the bound on the circumradii, we are able to bound the deviation of
normals.

######  Lemma 4.13.

If $t_{ijk}$ is a guide triangle, then (1)
$\angle_{a}(n_{p_{i}},n_{p_{j}})\leq\eta_{s}\delta<0.47^{\circ}$, with
$\eta_{s}<2.03$, and (2)
$\angle_{a}(n_{t},n_{p_{i}})\leq\eta_{t}\delta<1.52^{\circ}$, with
$\eta_{t}<6.6$, where $n_{p_{i}}$ is the line normal to $\mathcal{M}$ at
$p_{i}$ and $n_{t}$ is the normal to $t_{ijk}$. In particular, $t_{ijk}$ makes
an angle at most $\eta_{t}\delta$ with $T_{p_{i}}$.

######  Proof 4.14.

4.9 implies $\textbf{d}(p_{i},p_{j})\leq\kappa\delta\textrm{lfs}(p_{i})$ and
(1) follows from the Normal Variation Lemma [14] with $\rho=\kappa\delta<1/3$
yielding $\angle_{a}(n_{p_{i}},n_{p_{j}})\leq\kappa\delta/(1-\kappa\delta)$.
Letting $R_{t}$ denote the circumradius of $t$, 4.11 implies that the
$R_{t}\leq\varrho_{f}\cdot\delta\textrm{lfs}(p_{i})\leq\textrm{lfs}(p_{i})/\sqrt{2}$
and the Triangle Normal Lemma [31] implies
$\angle_{a}(n_{p^{\ast}},n_{t})<4.57\delta<1.05^{\circ}$, where $p^{\ast}$ is
the vertex of $t$ subtending a maximal angle in $t$. Hence,
$\angle_{a}(n_{p_{i}},n_{t})\leq\angle_{a}(n_{p_{i}},n_{p^{\ast}})+\angle_{a}(n_{p^{\ast}},n_{t})$.

Towards establishing homeomorphism, the next lemma on the monotonicity of
distance to the nearest seed is critical. First, we show that the nearest
seeds to any surface point $x\in\mathcal{M}$ are generated by nearby samples.

######  Lemma 4.15.

The nearest seed to $x\in\mathcal{M}$ lies on some $\partial B_{i}$ where
$\textbf{d}(x,p_{i})\leq 5.03\cdot\epsilon\textrm{lfs}(x)$. Consequently,
$\textbf{d}(x,p_{i})\leq 5.08\cdot\epsilon\textrm{lfs}(p_{i})$.

######  Proof 4.16.

In an $\epsilon$-sampling, there exists a $p_{a}$ such that
$\textbf{d}(x,p_{a})\leq\epsilon\textrm{lfs}(x)$, where
$\textrm{lfs}(p_{a})\leq(1+\epsilon)\textrm{lfs}(x)$. The sampling conditions
also guarantee that there exists at least one seed $s_{a}$ on $\partial
B_{a}$. By the triangle inequality, we get that
$\textbf{d}(x,s_{a})\leq\textbf{d}(x,p_{a})+\textbf{d}(p_{a},s_{a})\leq\epsilon\textrm{lfs}(x)+\delta\textrm{lfs}(p_{a})\leq\epsilon(1+2(1+\epsilon))\textrm{lfs}(x)=\epsilon(2\epsilon+3)\textrm{lfs}(x)$.

We aim to bound $\ell$ to ensure $\forall p_{i}$ s.t.
$\textbf{d}(x,p_{i})=\ell\cdot\epsilon\textrm{lfs}(x)$, the nearest seed to
$x$ cannot lie on $B_{i}$. Note that in this case,
$(1-\ell\epsilon)\textrm{lfs}(x)\leq\textrm{lfs}(p_{i})\leq(1+\ell\epsilon)\textrm{lfs}(x)$.
Let $s_{i}$ be any seed on $B_{i}$. It follows that
$\textbf{d}(x,s_{i})\geq\textbf{d}(x,p_{i})-\textbf{d}(p_{i},s_{i})\geq\ell\cdot\epsilon\textrm{lfs}(x)-2\epsilon\textrm{lfs}(p_{i})\geq\epsilon\big{(}(1-2\epsilon)\ell-2\big{)}\textrm{lfs}(x)$.

Setting
$\epsilon\big{(}(1-2\epsilon)\ell-2\big{)}\textrm{lfs}(x)\geq\epsilon(2\epsilon+3)\textrm{lfs}(x)$
suffices to ensure $\textbf{d}(x,s_{i})\geq\textbf{d}(x,s_{a})$, and we get
$\ell\geq(2\epsilon+5)/(1-2\epsilon)$. Conversely, if the nearest seed to $x$
lies on $B_{i}$, it must be the case that
$\textbf{d}(x,p_{i})\leq\ell\epsilon\textrm{lfs}(x)$. We verify that
$\ell\epsilon=\epsilon(2\epsilon+5)/(1-2\epsilon)<1$ for any $\epsilon<0.13$.
It follows that
$\textbf{d}(x,p_{j})\leq\ell\epsilon/(1-\ell\epsilon)\textrm{lfs}(p_{i})$.

######  Lemma 4.17.

For any normal segment $N_{x}$ issued from $x\in\mathcal{M}$, the distance to
$\mathcal{S}^{\uparrow}$ is either strictly increasing or strictly decreasing
along $\Gamma^{-1}([0,0.96\epsilon])\cap N_{x}$. The same holds for
$\mathcal{S}^{\downarrow}$.

######  Proof 4.18.

Let $n_{x}$ be the outward normal and $T_{x}$ be the tangent plane to
$\mathcal{M}$ at $x$. By 4.15, the nearest seeds to $x$ are generated by
nearby samples. Fix one such nearby sample $p_{i}$. For all possible locations
of a seed $s\in\mathcal{S}^{\uparrow}\cap\partial B_{i}$, we will show a
sufficiently large lower bound on $\langle s-s^{\prime\prime},n_{x}\rangle$,
where $s^{\prime\prime}$ the projection of $s$ onto $T_{x}$.

Take $\textrm{lfs}(p_{i})=1$ and let $B_{s}=\mathbb{B}(c,1)$ be the tangent
ball to $\mathcal{M}$ at $p_{i}$ with $s\in B_{s}$. Let $A$ be the plane
containing $\\{p_{i},s,x\\}$. Assume in the worst case that $A\bot T_{p_{i}}$
and $x$ is as far as possible from $p_{i}$ on $\partial B_{s}\cap T_{p_{i}}$.
By 4.15, $\textbf{d}(p_{i},x)\leq 5.08\epsilon$ and it follows that
$\theta_{x}=\angle(n_{x},n_{p_{i}})\leq 5.08\epsilon/(1-5.08\epsilon)\leq
5.14\epsilon$. This means that $T_{x}$ is confined within a
$(\pi/2-\theta_{x})$-cocone centered at $x$. Assume in the worst case that
$n_{x}$ is parallel to $A$ and $T_{x}$ is tilted to minimize
$\textbf{d}(s,s^{\prime\prime})$; see Figure 5(b).

Let $T^{\prime}_{x}$ be a translation of $T_{x}$ such that $p_{i}\in
T^{\prime}_{x}$ and denote by $x^{\prime}$ and $s^{\prime}$ the projections of
$x$ and $s$, respectively, onto $T^{\prime}_{x}$. Observe that
$T^{\prime}_{x}$ makes an angle $\theta_{x}$ with $T_{p_{i}}$. From the
isosceles triangle $\triangle p_{i}cx$, we get that $\theta^{\prime}_{x}\leq
1/2\angle p_{i}cx=\sin^{-1}{5.08\epsilon/2}\leq 2.54\epsilon$. Now, consider
$\triangle p_{i}xx^{\prime}$ and let $\phi=\angle xp_{i}x^{\prime}$. We have
that $\phi=\theta_{x}+\theta^{\prime}_{x}\leq
2.54\epsilon+\delta/(1-\delta)\leq 4.55\epsilon$. Hence, $\sin(\phi)\leq
4.55\epsilon$ and $\textbf{d}(x,x^{\prime})\leq 5.08\epsilon\sin(\phi)\leq
0.05\epsilon$. On the other hand, we have that $\angle
sp_{i}s^{\prime}=\psi\geq\theta_{s}-\theta_{x}$ and
$\textbf{d}(s,s^{\prime})\geq\delta\sin\psi$, where $\theta_{s}\geq
1/2-5\epsilon$ by 4.7. Simplifying we get $\sin(\psi)\geq 1/2-10.08\epsilon$.
The proof follows by evaluating
$\textbf{d}(s,s^{\prime\prime})=\textbf{d}(s,s^{\prime})-\textbf{d}(x,x^{\prime})$.

(a) Seed elevation $\theta_{s}$.

(b) Bounding seed height above $T_{x}$.

(c) Bounding $\textbf{d}(q,\mathcal{M})$.

Figure 5. Constructions used for (a) 4.7, (b) 4.17 and (c) Theorem 4.19.

######  Theorem 4.19.

For every $x\in\mathcal{M}$ with closest point $q\in\hat{\mathcal{M}}$, and
for every $q\in\hat{\mathcal{M}}$ with closest point $x\in\mathcal{M}$, we
have $\|xq\|<h_{t}\cdot\epsilon^{2}\textrm{lfs}(x)$, where $h_{t}<30.52$. For
$\epsilon<1/500$, $h_{t}\cdot\epsilon^{2}<0.0002$. Moreover, the restriction
of the mapping $\pi$ to $\hat{\mathcal{M}}$ is a homeomorphism and
$\hat{\mathcal{M}}$ and $\mathcal{M}$ are ambient isotopic. Consequently,
$\hat{\mathcal{O}}$ is ambient isotopic to $\mathcal{O}$ as well.

######  Proof 4.20.

Fix a sample $p_{i}\in\mathcal{P}$ and a surface point $x\in\mathcal{M}\cap
B_{i}$. We consider two cocones centered at $x$: a $p$-cocone contains all
nearby surface points and a $q$-cocone contains all guide triangles incident
at $p_{i}$. By Theorem 3.1, all reconstruction facets generated by seeds on
$B_{i}$ are sandwiched in the $q$-cocone.

4.13 readily provides a bound on the q-cocone angle as
$\gamma\leq\eta_{t}\delta$. In addition, since
$\textbf{d}(p_{i},x)\leq\delta\textrm{lfs}(p_{i})$, we can bound the
$p$-cocone angle as $\theta\leq 2\sin^{-1}{(\delta/2)}$ by Lemma 2 in [7]. We
utilize a mixed $pq$-cocone with angle $\omega=\gamma/2+\theta/2$, obtained by
gluing the lower half of the $p$-cocone with the upper half of the $q$-cocone.

Let $q\in\hat{\mathcal{M}}$ and consider its closest point $x\in\mathcal{M}$.
Again, fix $p_{i}\in\mathcal{P}$ such that $x\in B_{i}$; see Figure 5(c). By
sandwiching, we know that any ray through $q$ intersects at least one guide
triangle, in some point $y$, after passing through $x$. Let us assume the
worst case that $y$ lies on the upper boundary of the $pq$-cocone. Then,
$\textbf{d}(q,x)\leq\textbf{d}(y,y^{\prime})=h=\delta\sin(\omega)\textrm{lfs}(p_{i})$,
where $y^{\prime}$ is the closest point on the lower boundary of the
$pq$-cocone point to $q$. We also have that,
$\textbf{d}(p_{i},x)\leq\cos(\omega)\delta\textrm{lfs}(p_{i})\leq\delta\textrm{lfs}(p_{i})$,
and since lfs is 1-Lipschitz,
$\textrm{lfs}(p_{i})\leq\textrm{lfs}(x)/(1-\delta)$. Simplifying, we write
$\textbf{d}(q,x)<\delta\omega/(1-\delta)\cdot\textrm{lfs}(x)<h_{t}\epsilon^{2}\textrm{lfs}(x)$.

With $\textbf{d}(q,x)\leq 0.55\epsilon\textrm{lfs}(x)$, 4.17 shows that the
normal line from any $p\in\mathcal{M}$ intersects $\hat{\mathcal{M}}$ exactly
once close to the surface. It follows that for every point $x\in\mathcal{M}$
with closest point $q\in\hat{\mathcal{M}}$, we have
$\textbf{d}(x,q)\leq\textbf{d}(x,q^{\prime})$ where
$q^{\prime}\in\hat{\mathcal{M}}$ with $x$ its closest point in $\mathcal{M}$.
Hence, $\textbf{d}(x,q)\leq h_{t}\epsilon^{2}\textrm{lfs}(x)$ as well.

Building upon 4.17, as a point moves along the normal line at $x$, it is
either the case that the distance to $\mathcal{S}^{\uparrow}$ is decreasing
while the distance to $\mathcal{S}^{\downarrow}$ is increasing or the other
way around. It follows that these two distances become equal at exactly one
point on the Voronoi facet above or below $x$ separating some seed
$s^{\uparrow}\in\mathcal{S}^{\uparrow}$ from another seed
$s^{\downarrow}\in\mathcal{S}^{\downarrow}$. Hence, the restriction of the
mapping $\pi$ to $\hat{\mathcal{M}}$ is a homeomorphism.

This shows that $\hat{\mathcal{M}}$ and $\mathcal{M}$ homeomorphic. Recall
that 4.1(3) implies $\mathcal{U}$ is a topological thickening [25] of
$\mathcal{M}$. In addition, Theorem 3.1 guarantees that $\hat{\mathcal{M}}$ is
embedded in the interior of $\mathcal{U}$, such that it separates the two
surfaces comprising $\partial\mathcal{U}$. These three properties imply
$\hat{\mathcal{M}}$ is isotopic to $\mathcal{M}$ in $\mathcal{U}$ by virtue of
Theorem 2.1 in [25]. Finally, as $\hat{\mathcal{M}}$ is the boundary of
$\hat{\mathcal{O}}$ by definition, it follows that $\hat{\mathcal{O}}$ is
isotopic to $\mathcal{O}$ as well.

##  5\. Quality guarantees and output size

We establish a number of quality guarantees on the output mesh. The main
result is an upper bound on the _fatness_ of all Voronoi cell. See Appendix B
for the proofs.

Recall that fatness is the outradius to inradius ratio, where the outradius is
the radius of the smallest enclosing ball, and the inradius is the radius of
the largest enclosed ball. The good quality of guide triangles allows us to
bound the inradius of Voronoi cells.

######  Lemma 5.1.

For all guide triangles $t_{ijk}$: (1) Edge length ratios are bounded:
$\ell_{k}/\ell_{j}\leq\kappa_{\ell}=\frac{2\delta}{1-\delta}\frac{\sigma\epsilon}{1+\sigma\epsilon}.$
(2) Angles are bounded: $\sin(\theta_{i})\geq 1/(2\overline{\varrho}_{f})$
implying $\theta_{i}\in(7.8^{\circ},165^{\circ})$. (3) Altitudes are bounded:
the altitude above $e_{ij}$ is at least $\alpha_{t}|e_{ij}|$, where
$\alpha_{t}=1/4\overline{\varrho}_{f}>0.067$.

Observe that a guide triangle is contained in the Voronoi cell of its seed,
even when one of the guides is covered. Hence, the tetrahedron formed by the
triangle together with its seed lies inside the cell, and the cell inradius is
at least the tetrahedron inradius.

######  Lemma 5.2.

For seeds $s_{ijk}\in\mathcal{S}^{\uparrow}\cup\mathcal{S}^{\downarrow}$, the
inradius of the Voronoi cell is at least
$\varrho_{v}\delta\cdot\textrm{lfs}(p_{i})$ with
$\varrho_{v}=\hat{h}_{s}/(1+\frac{3}{2\sigma\overline{\varrho}_{f}})>0.3$ and
$\hat{h}_{s}\geq\frac{1}{2}-(5+2\eta_{t})\epsilon$.

To get an upper bound on cell outradii, we must first generate seeds interior
to $\mathcal{O}$. We consider a simple algorithm for generating
$\mathcal{S}^{\downarrow\downarrow}$ based on a standard octree over
$\mathcal{O}$. For sizing, we extend lfs beyond $\mathcal{M}$, using the
point-wise maximal 1-Lipschitz extension
$\textrm{lfs}(x)=\inf_{p\in\mathcal{M}}(\textrm{lfs}(p)+\textbf{d}(x,p))$
[44]. An octree box $\square$ is refined if the length of its diagonal is
greater than $2\delta\cdot\textrm{lfs}(c)$, where $c$ is the center of
$\square$. After refinement terminates, we add an interior seed at the center
of each empty box, and do nothing with boxes containing one or more guide
seeds. Applying this scheme, we obtain the following.

######  Lemma 5.3.

The fatness of interior cells is at most
$\frac{8\sqrt{3}(1+\delta)}{1-3\delta}<14.1$.

######  Lemma 5.4.

The fatness of boundary cells is at most
$\frac{4(1+\delta)}{(1-3\delta)(1-\delta)^{2}\varrho_{v}}<13.65$.

As the integral of $\textrm{lfs}^{-3}$ is bounded over a single cell, it
effectively counts the seeds.

######  Lemma 5.5.

$|\mathcal{S}^{\downarrow\downarrow}|\leq
18\sqrt{3}/\pi\cdot\epsilon^{-3}\int_{\mathcal{O}}\textrm{lfs}^{-3}$.

##  6\. Conclusions

We have analyzed an abstract version of the VoroCrust algorithm for volumes
bounded by smooth surfaces. We established several guarantees on its output,
provided the input samples satisfy certain conditions. In particular, the
reconstruction is isotopic to the underlying surface and all 3D Voronoi cells
have bounded fatness, i.e., outradius to inradius ratio. The triangular faces
of the reconstruction have bounded angles and edge-length ratios, except
perhaps in the presence of slivers. In a forthcoming paper [3], we describe
the design and implementation of the complete VoroCrust algorithm, which
generates conforming Voronoi meshes of realistic models, possibly containing
sharp features, and produces samples that follow a natural sizing function and
ensure output quality.

For future work, it would be interesting to ensure both guides are uncovered,
or both covered. The significance would be that no tetrahedral slivers arise
and no Steiner points are introduced. Further, the surface reconstruction
would be composed entirely of guide triangles, so it would be easy to show
that triangle normals converge to surface normals as sample density increases.
Alternatively, where Steiner points are introduced on the surface, it would be
helpful to have conditions that guaranteed the triangles containing Steiner
points have good quality. In addition, the minimum edge length in a Voronoi
cell can be a limiting factor in certain numerical solvers. Post-processing by
mesh optimization techniques [5, 53] can help eliminate short Voronoi edges
away from the surface. Finally, we expect that the abstract algorithm analyzed
in this paper can be extended to higher dimensions.

## References

  * [1] A. Abdelkader, C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi.  Sampling conditions for conforming Voronoi meshing by the VoroCrust algorithm.  In 34th International Symposium on Computational Geometry (SoCG 2018), pages 1:1–1:16, 2018.
  * [2] A. Abdelkader, C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi.  VoroCrust Illustrated: Theory and Challenges (Multimedia Contribution).  In 34th International Symposium on Computational Geometry (SoCG 2018), pages 77:1–77:4, 2018.
  * [3] A. Abdelkader, C. Bajaj, M. Ebeida, A. Mahmoud, S. Mitchell, J. Owens, and A. Rushdi.  VoroCrust: Voronoi meshing without clipping.  Manuscript, In preparation.
  * [4] A. Abdelkader, C. Bajaj, M. Ebeida, and S. Mitchell.  A Seed Placement Strategy for Conforming Voronoi Meshing.  In Canadian Conference on Computational Geometry, 2017.
  * [5] A. Abdelkader, A. Mahmoud, A. Rushdi, S. Mitchell, J. Owens, and M. Ebeida.  A constrained resampling strategy for mesh improvement.  Computer Graphics Forum, 36(5):189–201, 2017.
  * [6] O. Aichholzer, F. Aurenhammer, B. Kornberger, S. Plantinga, G. Rote, A. Sturm, and G. Vegter.  Recovering structure from r-sampled objects.  Computer Graphics Forum, 28(5):1349–1360, 2009.
  * [7] N. Amenta and M. Bern.  Surface reconstruction by Voronoi filtering.  Discrete & Computational Geometry, 22(4):481–504, December 1999\.
  * [8] N. Amenta, M. Bern, and D. Eppstein.  The crust and the $\beta$-skeleton: Combinatorial curve reconstruction.  Graphical models and image processing, 60(2):125–135, 1998.
  * [9] N. Amenta, M. Bern, and D. Eppstein.  Optimal point placement for mesh smoothing.  Journal of Algorithms, 30(2):302–322, 1999.
  * [10] N. Amenta, M. Bern, and M. Kamvysselis.  A new Voronoi-based surface reconstruction algorithm.  In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, pages 415–421, 1998.
  * [11] N. Amenta, S. Choi, T. Dey, and N. Leekha.  A simple algorithm for homeomorphic surface reconstruction.  In 16th Annual Symposium on Computational Geometry, pages 213–222, 2000.
  * [12] N. Amenta, S. Choi, and R.-K. Kolluri.  The power crust.  In Proceedings of the Sixth ACM Symp. on Solid Modeling and Applications, pages 249–266, 2001.
  * [13] N. Amenta, S. Choi, and R.-K. Kolluri.  The power crust, unions of balls, and the medial axis transform.  Computational Geometry, 19(2):127–153, July 2001.
  * [14] N. Amenta and T. Dey.  Normal variation for adaptive feature size.  CoRR, abs/1408.0314, 2014.
  * [15] N. Amenta and R.-K. Kolluri.  The medial axis of a union of balls.  Computational Geometry, 20(1):25 – 37, 2001.  Selected papers from the 12th Annual Canadian Conference.
  * [16] N. Amenta, T. Peters, and A. Russell.  Computational topology: ambient isotopic approximation of 2-manifolds.  Theoretical Computer Science, 305(1):3 – 15, 2003.  Topology in Computer Science.
  * [17] L. Beirão da Veiga, F. Brezzi, L.-D. Marini, and A. Russo.  The hitchhiker’s guide to the virtual element method.  Mathematical Models and Methods in Applied Sciences, 24(08):1541–1573, 2014.
  * [18] N. Bellomo, F. Brezzi, and G. Manzini.  Recent techniques for PDE discretizations on polyhedral meshes.  Mathematical Models and Methods in Applied Sciences, 24(08):1453–1455, 2014.
  * [19] F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, and G. Taubin.  The ball-pivoting algorithm for surface reconstruction.  IEEE Transactions on Visualization and Computer Graphics, 5(4):349–359, Oct 1999.
  * [20] J. Bishop.  Simulating the pervasive fracture of materials and structures using randomly close packed Voronoi tessellations.  Computational Mechanics, 44(4):455–471, September 2009.
  * [21] J.-D. Boissonnat and S. Oudot.  Provably good sampling and meshing of surfaces.  Graphical Models, 67(5):405 – 451, 2005.  Solid Modeling and Applications.
  * [22] T. Brochu, C. Batty, and R. Bridson.  Matching fluid simulation elements to surface geometry and topology.  ACM Trans. Graph., 29(4):47:1–47:9, 2010.
  * [23] F. Cazals, T. Dreyfus, S. Sachdeva, and N. Shah.  Greedy geometric algorithms for collection of balls, with applications to geometric approximation and molecular coarse-graining.  Computer Graphics Forum, 33(6):1–17, 2014.
  * [24] F. Cazals, H. Kanhere, and S. Loriot.  Computing the volume of a union of balls: A certified algorithm.  ACM Trans. Math. Softw., 38(1):3:1–3:20, 2011.
  * [25] F. Chazal and D. Cohen-Steiner.  A condition for isotopic approximation.  Graphical Models, 67(5):390 – 404, 2005.  Solid Modeling and Applications.
  * [26] F. Chazal and A. Lieutier.  Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees.  Computational Geometry, 40(2):156 – 170, 2008.
  * [27] S.-W. Cheng, T. Dey, H. Edelsbrunner, M. Facello, and S.-H. Teng.  Silver exudation.  J. ACM, 47(5):883–904, September 2000.
  * [28] S.-W. Cheng, T. Dey, and J. Shewchuk.  Delaunay Mesh Generation.  CRC Press, 2012.
  * [29] D. Cohen-Steiner, É.-C. de Verdière, and M. Yvinec.  Conforming Delaunay triangulations in 3D.  In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, SCG ’02, pages 199–208, 2002.
  * [30] K. Sykes D. Letscher.  On the stability of medial axis of a union of disks in the plane.  In 28th Canadian Conference on Computational Geometry, CCCG 2016, pages 29–33, 2016.
  * [31] T. Dey.  Curve and Surface Reconstruction: Algorithms with Mathematical Analysis.  Cambridge University Press, New York, NY, USA, 2006.
  * [32] T. Dey, K. Li, E. Ramos, and R. Wenger.  Isotopic reconstruction of surfaces with boundaries.  In Computer Graphics Forum, volume 28:5, pages 1371–1382, 2009\.
  * [33] T. Dey and L. Wang.  Voronoi-based feature curves extraction for sampled singular surfaces.  Computers & Graphics, 37(6):659–668, October 2013.  Shape Modeling International (SMI) Conference 2013.
  * [34] L. Duan and F. Lafarge.  Image partitioning into convex polygons.  In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3119–3127, June 2015.
  * [35] M. Ebeida and S. Mitchell.  Uniform random Voronoi meshes.  In International Meshing Roundtable (IMR), pages 258–275, 2011\.
  * [36] H. Edelsbrunner.  Weighted alpha shapes.  University of Illinois at Urbana-Champaign, Department of Computer Science, 1992.
  * [37] H. Edelsbrunner.  The union of balls and its dual shape.  Discrete & Computational Geometry, 13(3):415–440, Jun 1995.
  * [38] H. Edelsbrunner and E.-P. Mücke.  Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.  ACM Trans. Graph., 9(1):66–104, January 1990.
  * [39] R. Eymard, T. Gallouët, and R. Herbin.  Finite volume methods.  In Techniques of Scientific Computing (Part 3), volume 7 of Handbook of Numerical Analysis, pages 713 – 1018. Elsevier, 2000.
  * [40] Ø. Klemetsdal, R. Berge, K.-A. Lie, H. Nilsen, and O. Møyner.  SPE-182666-MS, chapter Unstructured Gridding and Consistent Discretizations for Reservoirs with Faults and Complex Wells.  Society of Petroleum Engineers, 2017.
  * [41] D. Kuzmin.  A guide to numerical methods for transport equations.  University Erlangen-Nuremberg, 2010.
  * [42] G. Manzini, A. Russo, and N. Sukumar.  New perspectives on polygonal and polyhedral finite element methods.  Mathematical Models and Methods in Applied Sciences, 24(08):1665–1699, 2014.
  * [43] R. Merland, G. Caumon, B. Lévy, and P. Collon-Drouaillet.  Voronoi grids conforming to 3D structural features.  Computational Geosciences, 18(3):373–383, 2014.
  * [44] G. Miller, D. Talmor, and S.-H. Teng.  Data generation for geometric algorithms on non-uniform distributions.  International Journal of Computational Geometry and Applications, 09(06):577–597, 1999.
  * [45] M. Murphy, D. Mount, and C. Gable.  A point-placement strategy for conforming Delaunay tetrahedralization.  International Journal of Computational Geometry & Applications, 11(06):669–682, 2001.
  * [46] P. Niyogi, S. Smale, and S. Weinberger.  Finding the homology of submanifolds with high confidence from random samples.  Discrete & Computational Geometry, 39(1-3):419–441, 2008.
  * [47] A. Okabe, B. Boots, K. Sugihara, and S.-N. Chiu.  Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, volume 501.  John Wiley & Sons, 2009.
  * [48] M. Peric and S. Ferguson.  The advantage of polyhedral meshes.  Dynamics - Issue 24, page 4–5, Spring 2005.  The customer magazine of the CD-adapco Group, currently maintained by Siemens at http://siemens.com/mdx. The issue is available at http://mdx2.plm.automation.siemens.com/magazine/dynamics-24 (accessed March 29, 2018).
  * [49] A. Rand and N. Walkington.  Collars and intestines: Practical conforming Delaunay refinement.  In Proceedings of the 18th International Meshing Roundtable, pages 481–497, 2009.
  * [50] C. Rycroft.  Voro++: A three-dimensional Voronoi cell library in C++.  Chaos, 19(4):–, 2009.  Software available online at http://math.lbl.gov/voro++/.
  * [51] M. Sents and C. Gable.  Coupling LaGrit Unstructured Mesh Generation and Model Setup with TOUGH2 Flow and Transport.  Comput. Geosci., 108(C):42–49, 2017.
  * [52] H. Si, K. Gärtner, and J. Fuhrmann.  Boundary conforming Delaunay mesh generation.  Computational Mathematics and Mathematical Physics, 50(1):38–53, 2010.
  * [53] D. Sieger, P. Alliez, and M. Botsch.  Optimizing Voronoi diagrams for polygonal finite element computations.  In International Meshing Roundtable (IMR), pages 335–350. Springer, 2010.
  * [54] P. Stelldinger.  Topologically correct surface reconstruction using alpha shapes and relations to ball-pivoting.  In Pattern Recognition, 2008. ICPR 2008. 19th International Conference on, pages 1–4. IEEE, 2008.
  * [55] D.-M. Yan, W. Wang, B. Lévy, and Y. Liu.  Efficient computation of clipped Voronoi diagram for mesh generation.  Computer-Aided Design, 45(4):843–852, April 2013.
  * [56] Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang.  Isotropic remeshing with fast and exact computation of restricted Voronoi diagram.  Computer Graphics Forum, 28(5):1445–1454, July 2009.
  * [57] M. Yip, J. Mohle, and J. Bolander.  Automated modeling of three-dimensional structural components using irregular lattices.  Computer-Aided Civil and Infrastructure Engineering, 20(6):393–407, 2005.

##  Appendix A Sandwich analysis

This appendix provides the proof of Theorem 3.1. In what follows, we assume
all sample spheres have disk caps; see Section 3.2. By Section 3.2, each
$p_{i}\in\mathcal{P}$ appears as a vertex in the surface reconstruction
$\hat{\mathcal{M}}$. For an appropriate sampling, $\hat{\mathcal{M}}$ is
watertight and the set of reconstruction facets containing $p_{i}$ is a
topological disk with $p_{i}$ in its interior. We seek to characterize the
angular orientation of the fan-facets around a sample $p_{i}$, namely that
they lie sandwiched between upper and lower guide triangles. For orientation,
it suffices to consider only the seeds on $\partial B_{i},$ because these are
the seeds whose cells contain $p_{i}$. By suppressing other seeds, the fan-
facets are all triangles extending radially from $p_{i}$ to infinity. To argue
about the actual reconstruction $\hat{\mathcal{M}}$, those other seeds are
introduced later.

We make use of technical arguments in spherical geometry concerning the
spherical arcs formed by the intersections of $\partial B_{i}$ with extended
reconstruction facets, and extended guide triangles. These arcs are great
circle arcs between the two points where $\partial B_{i}$ intersects the two
rays from $p_{i}$ that bound the extended triangle (facet).

For a reconstruction facet $t\in\hat{\mathcal{M}}$ incident to
$p_{i}\in\mathcal{P}$, let $\hat{t}$ be its radial extension from $p_{i}$ to
infinity. Similarly, we denote by $\hat{t}_{ijk}$ the radial extension of the
guide triangle $t_{ijk}$. An _extended fan-facet point_ is any point
$m\in\hat{t}\cap\partial B_{i}$. We will show that such points $m$ lie
sandwiched between extended guide triangles incident to $p_{i}$. Since $t$ is
the intersection of the Voronoi cells of one upper and one lower seed,
$m\in\hat{t}$ is the center of a Voronoi ball $B_{m}$ having those two seeds
on its boundary and no seed in its interior. The intersection of the empty
ball $B_{m}$ with $\partial B_{1}$ is the spherical disk $D_{m}\subset\partial
B_{1}$, and also has an interior $\overline{D}_{m}$ empty of seeds. The
following technical lemma is essential to the sandwiching arguments.

######  Lemma 1 (Path $m$ to $s$ misses $K$).

If all sample balls have disk caps, then for any $m$ on an extended
reconstruction facet $\hat{t}$ having $p_{i}\in\mathcal{P}$ as a vertex, the
shorter great circle arc on $\partial B_{i}$ from $m$ to the lower (upper)
seed of $t$ does not pass through the uppler (lower) cap.

######  Proof A.1.

We use numerals to index the unusually large number of samples and seeds
involved in the configurations at hand. Without loss of generality let $i=1$
and fix one such facet $t$. We consider up to seven spheres $\partial
B_{\\{2,\dots,8\\}}$, not necessarily distinct, intersecting $\partial B_{1}$.
Denote the upper and lower seeds associated with $t$ by ${s^{\uparrow}_{123}}$
and ${s^{\downarrow}_{145}}$. We show that
$\wideparen{m{s^{\downarrow}_{145}}}$ does not pass through
$K^{\uparrow}_{1}$; the case of $\wideparen{m{s^{\uparrow}_{123}}}$ and
$K^{\downarrow}_{1}$ is similar. The proof follows by examining great circle
arcs on $\partial B_{1}$ restricted within $D_{m}$. By the definition of disk
caps, $K^{\uparrow}_{1}$ is a topological disk and $\partial K^{\uparrow}_{1}$
forms a closed path. In addition $\partial K^{\uparrow}_{1}$ is disjoint from
$\partial K^{\downarrow}_{1}$, as $K^{\uparrow}_{1}$ and $K^{\downarrow}_{1}$
are separated by a medial band. Being a lower seed, ${s^{\downarrow}_{145}}$
lies on $\partial K^{\downarrow}_{1}$.

Suppose for contradiction that $\wideparen{m{s^{\downarrow}_{145}}}$ goes
through $K^{\uparrow}_{1}$ and let
$x\in\wideparen{m{s^{\downarrow}_{145}}}\subset\partial D_{m}$ be the last
point where $\wideparen{m{s^{\downarrow}_{145}}}$ crosses $\partial
K^{\uparrow}_{1}$ in the direction from the interior of $K^{\uparrow}_{1}$ to
its exterior. We have that $x$ lies on an uncovered arc
$\wideparen{{s^{\uparrow}_{167}}{s^{\uparrow}_{168}}}\subset\partial
K^{\uparrow}_{1}$ on the guide circle $C_{16}$ with seeds
${s^{\uparrow}_{167}}$ and ${s^{\uparrow}_{168}}$ as endpoints. Figure 6(a)
depicts a hypothetical path $\wideparen{m{s^{\downarrow}_{145}}}$. Since
$D_{m}$ is empty, ${s^{\uparrow}_{167}}$ and ${s^{\uparrow}_{168}}$ both lie
outside $D_{m}$. In addition, ${s^{\downarrow}_{145}}$ cannot lie inside
$C_{16}$, as ${s^{\downarrow}_{145}}$ is an uncovered seed and $C_{16}$ bounds
the region on $\partial B_{1}$ which is covered by $B_{6}$; this impossible
configuration is illustrated by the dashed circle in Figure 6(a). It would
follow that $\wideparen{m{s^{\downarrow}_{145}}}$ must cross
$\wideparen{{s^{\uparrow}_{167}}{s^{\uparrow}_{168}}}$ a second time to reach
${s^{\downarrow}_{145}}$, a contradiction to $x$ being the last point where
$\wideparen{m{s^{\downarrow}_{145}}}$ intersects $\partial K^{\uparrow}_{1}$.
(Special cases include $K^{\uparrow}_{1}$ and $K^{\downarrow}_{1}$ meeting at
a point, or $x$ being a point of tangency between $C_{16}$ and
$\wideparen{m{s^{\downarrow}_{145}}}$.)

(a) 1: arcs from extended reconstruction $m$ to ${s^{\downarrow}}$ cannot
cross $K^{\uparrow}$.

(b) 2: $m$’s hypothetical locations above $\hat{t}_{123}$: upper cap
$K^{\uparrow}_{1}$, $R_{1}$ and $R_{2}$.

(c) 2: $m\notin R_{1}$.

(d) 2: $m\notin R_{2}$ (1).

(e) 2: $m\notin R_{2}$ (2).

Figure 6. Fan-facet sandwich lemmas.

A reconstructed fan-facet is _sandwiched_ at $p_{i}$ if the intersection of
its radial extension with $\partial B_{i}$ lies in the region bounded by the
extension of guide triangles incident to $p_{i}$.

######  Lemma 2 (Sandwich fan-facets).

If all sample balls have disk caps, then all facets in $\hat{\mathcal{M}}$
with a sample $p_{i}\in\mathcal{P}$ as a vertex are sandwiched between guide
triangles.

######  Proof A.2.

Take $i=1$ and consider the spherical arcs on $\partial B_{1}$ which arise
from intersecting $\partial B_{1}$ with extended guide triangles having
$p_{1}$ as a vertex. We partition the subset of $\partial B_{1}$ above these
arcs, and show that no point $m$ of an extended reconstruction facet can lie
in any of these partitions; the argument for the subset of $\partial B_{1}$
below these arcs is analogous. By Lemma 1, such $m$ may only lie on the medial
band.

Consider the spherical arcs bounding the upper cap $K^{\uparrow}_{1}$. As in
the proof of the prior lemma, we label up to seven other spheres $\partial
B_{\\{2,\dots,7\\}}$ that intersect $\partial B_{1}$. Each consecutive pair of
such arcs intersect at an upper seed ${s^{\uparrow}_{\ast}}$ and a lower guide
${g^{\downarrow}_{*}}$ which may or may not be covered. Fix such an arc
$\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{124}}}\subset\partial
K^{\uparrow}_{1}$ on the guide circle $C_{12}$. With a slight abuse of
notation, we denote by $e_{1j}$ the intersection of the ray
$\overrightarrow{p_{1}p_{j}}$ with $\partial B_{1}$. Let $D_{1j}$ denote the
spherical disk bounded by $C_{1j}$ and $\overline{D}_{1j}$ its interior. We
split $D_{12}$ in half by the great circle arc through $e_{12}$ bisecting
$\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{124}}}$. Without loss of
generality, we consider the half disk containing ${s^{\uparrow}_{123}}$ and
argue that no point $m$ on an extended reconstruction facet can lie above the
extended upper guide triangle $\hat{t}_{123}$; the case of lower guide
triangles is similar.

We partition the half disk above the extended upper guide triangle
$\hat{t}_{123}$ into $R_{1}$, above $\wideparen{e_{12}{s^{\uparrow}_{123}}}$
and $R_{2}$, below $\wideparen{e_{12}{s^{\uparrow}_{123}}}$ and above the
extended upper guide facet $\hat{t}_{123}$. See Figure 6(b). Suppose there is
some point $m$ on an extended reconstruction facet whose two closest and
equidistant seeds are ${s^{\uparrow}_{123}}$ and some lower seed which we
denote by ${s^{\downarrow}_{156}}$. We show that $m$ cannot lie above
$\hat{t}_{123}$, neither in $R_{1}$ nor $R_{2}$. Observe that if $m=e_{12}$,
then it clearly does not lie above $\hat{t}_{123}$. Hence, we assume $m\neq
e_{12}$.

Suppose $m\in R_{1}$ and consider the spherical disk $D_{m}$ on $\partial
B_{1}$, with center $m$ and ${s^{\uparrow}_{123}}$ on its boundary. As no seed
is closer to $m$ than ${s^{\uparrow}_{123}}$, $D_{m}$ is empty of other seeds
and cannot contain ${s^{\uparrow}_{124}}$ in its interior. Hence, the only
portion of $D_{m}$ outside $D_{12}$ is bounded by
$\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{124}}}$; see Figure 6(c). In
addition, ${s^{\downarrow}_{156}}$ cannot lie in $\overline{D}_{12}$. It
follows that the shorter great circle arc from $m$ to
${s^{\downarrow}_{156}}\in\partial D_{m}\setminus\overline{D}_{12}$ must cross
$\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{124}}}\subset\partial
K^{\uparrow}_{1}$ into the upper cap $K^{\uparrow}_{1}$; a contradiction to 1.
We conclude that $m\notin R_{1}$.

Suppose $m\in R_{2}$ and consider the spherical disk $D_{13}$ centered at
$e_{13}$ with ${s^{\uparrow}_{123}}$ on its boundary and no seed in its
interior. We have two subcases: either $D_{m}\subset D_{12}\cup D_{13}$ or
not. Suppose $D_{m}\subset D_{12}\cup D_{13}$; see Figure 6(d). It would
follow that the only possible position for ${s^{\downarrow}_{156}}$ is
${g^{\downarrow}_{123}}$. But then,
$m\in\wideparen{e_{12}e_{13}}\subset\hat{t}_{123}$; a contradiction to $m\in
R_{2}$. In the second subcase, let ${s^{\uparrow}_{137}}$ be the other seed on
$C_{13}$ such that
$\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{137}}}\subset\partial
K^{\uparrow}_{1}$; see Figure 6(e). As in the case when $m$ was assumed to lie
in $R_{1}$, the only portion of $D_{m}$ outside $D_{12}\cup D_{13}$ is bounded
by $\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{137}}}$ where
${s^{\downarrow}_{156}}$ cannot lie in
$\overline{D}_{12}\cup\overline{D}_{13}$. It follows that the shorter great
circle arc from $m$ to ${s^{\downarrow}_{156}}\in\partial
D_{m}\setminus(\overline{D}_{12}\cup\overline{D}_{13})$, must cross
$\wideparen{{s^{\uparrow}_{123}}{s^{\uparrow}_{137}}}\subset\partial
K^{\uparrow}_{1}$ into $K^{\uparrow}_{1}$; a contradiction to 1. As neither
subcase can be true, we conclude $m\notin R_{2}$.

See 3.1

######  Proof A.3.

Let $V_{ijk}$ denote the Voronoi cell of seed $s_{ijk}$ and
$\mathcal{P}_{ijk}=\\{p_{i},p_{j},p_{k}\\}$. By Section 3.2, all three samples
$\mathcal{P}_{ijk}$ appear as Voronoi vertices of $V_{ijk}$ and are retained
as vertices in $\hat{\mathcal{M}}$. For an appropriate sampling,
$\hat{\mathcal{M}}$ is watertight and each sample is surrounded by a fan of
reconstruction facets. By 2, the reconstruction facets of each such fan are
sandwiched between the guide triangles incident on the corresponding sample.
In particular, the subset of such reconstruction facets on the boundary of
$V_{ijk}$ and incident on samples in $\mathcal{P}_{ijk}$, denoted by
$\mathcal{F}_{ijk}$, are sandwiched in this manner. We consider upper seeds;
the case of lower seeds is similar. As $V^{\uparrow}_{ijk}$ is convex, the
planes containing each of the facets in $\mathcal{F}^{\uparrow}_{ijk}$ are
tangents to $V^{\uparrow}_{ijk}$. By 2, the planes containing the subset of
guide triangles incident on each of the samples in $\mathcal{P}_{ijk}$, and
bounding the reconstruction facets in $\mathcal{F}^{\uparrow}_{ijk}$ from
below, are also tangents to $V^{\uparrow}_{ijk}$. Hence, all the Voronoi cells
of upper seeds lie above the guide triangles incident on samples in
$\mathcal{P}_{ijk}$. Similarly, all the Voronoi cells of lower seeds lie below
the upper guide triangles incident on the associated triplet of sample points.
As $\hat{\mathcal{M}}$ is the intersection of the Voronoi cells of upper and
lower seeds, it follows that $\hat{\mathcal{M}}$ is sandwiched between upper
and lower guide triangles, which constitute
$\partial\mathcal{J}(\mathcal{P})$.

##  Appendix B Quality bounds

This appendix provides the details of the proposed octree refinement for
seeding the interior of $\mathcal{O}$ along with the proofs of the statements
in Section 5. Namely, we bound the fatness of all cells in the Voronoi mesh
$\hat{\mathcal{O}}$ as well as a number of quality measures of guide triangles
which constitute the majority of facets in the surface reconstruction
$\hat{\mathcal{M}}$.

###  B.1. At the boundary

Recall that the seeds in
$\mathcal{S}^{\uparrow}\cup\mathcal{S}^{\downarrow}\subset\partial\mathcal{U}$
are used to define the surface reconstruction $\hat{\mathcal{M}}$ as the set
of Voronoi facets common to one seed from $\mathcal{S}^{\uparrow}$ and another
$\mathcal{S}^{\downarrow}$. Guide triangles contribute the majority of facets
in $\hat{\mathcal{M}}$. Thanks to the sparsity of the sampling, we can derive
several quality measures for guide triangles.

See 5.1

######  Proof B.1.

The edge ratio bound is basically a restatement of 4.9. Denote by $\ell_{i}$
and $\theta_{i}$ the length of the triangle edge opposite to $p_{i}$ and the
angle at vertex $p_{i}$, respectively. 4.9 implies
$\ell_{k}\leq\kappa\delta\textrm{lfs}(p_{i})$ and the sparsity condition
guarantees that $\ell_{j}\geq\kappa_{\epsilon}\textrm{lfs}(p_{i})$, hence
$\ell_{i}/\ell_{k}\leq\kappa_{\ell}$ for any pair of edges.

Let $R_{ijk}$ denote $t_{ijk}$’s circumradius. By the Central Angle Theorem,
$\sin(\theta_{i})=\ell_{i}/(2R_{ijk})$, and we also have
$R_{ijk}\leq\overline{\varrho}_{f}\ell_{i}$ from 4.11. Hence
$\sin(\theta_{i})\geq 1/(2\overline{\varrho}_{f})$.

For the worst case altitude, let the edge under consideration be the longest,
$e=\ell_{k}$, and the second longest edge $\ell_{j},$ so
$\ell_{j}\geq\ell_{k}/2$. The altitude is then
$\sin(\theta_{i})\ell_{j}\geq\ell_{k}/(4\overline{\varrho}_{f})$.

Before proceeding to study the decomposition of the interior of $\mathcal{O}$,
we establish a bound on the inradius of Voronoi cells with seeds in
$\mathcal{S}^{\uparrow}\cup\mathcal{S}^{\downarrow}$.

######  Corollary 1.

If $t_{ijk}$ is a guide triangle with associated seed $s$, then $\angle
sp_{i}s^{\prime\prime}\geq\frac{1}{2}-\eta^{\prime}_{t}\epsilon$, where
$s^{\prime\prime}$ is the projection of $s$ on the plane of $t_{ijk}$ and
$\eta^{\prime}_{t}\leq 5+2\eta_{t}<18.18$, implying
$\textbf{d}(s,s^{\prime\prime})\geq\hat{h}_{s}\delta\textrm{lfs}(p_{i})$ with
$\hat{h}_{s}\geq\frac{1}{2}-\eta^{\prime}_{t}\epsilon$.

######  Proof B.2.

Combining 4.7 with 4.13, we have $\angle sp_{i}s^{\prime\prime}\geq\angle
sp_{i}s^{\prime}-\angle_{a}(n_{t_{ijk}},n_{p_{i}})$.

See 5.2

######  Proof B.3.

Fix a seed $s_{ijk}$ and observe that $\\{p_{i},p_{j},p_{k}\\}$ belong to its
Voronoi cell. By the convexity of the cell, it follows that the tetrahedron
$T=p_{i}p_{j}p_{k}s_{ijk}$ is contained inside it. We establish a lower bound
on the cell’s inradius by bounding the inradius of $T$. Let $f_{i}$ denote the
facet of $T$ opposite to $p_{i}$ and $f_{0}$ denote $t_{ijk}$. Let $A_{i}$ be
the area of $f_{i}$.

Observe that the incenter $c_{T}$ divides $T$ into four smaller tetrahedra,
one for each facet of $T$, where the distance from $c_{T}$ to the plane of
each facet is equal to the inradius $r$. This allows us to express the volume
of $T$ as $V=\sum_{i=0}^{3}rA_{i}/3$. Hence, we have that
$r=3V/\sum_{i}A_{i}$. We may also express $V$ as $HA_{0}/3$, where $H$ is the
distance from $s_{ijk}$ to the plane of $t_{ijk}$. Substituting for $V$ and
factoring out $A_{0}$, we get that $r=H/(1+\sum_{i>0}^{3}A_{i}/A_{0})$.

Triangle area ratios $A_{i}/A_{0}$ are bounded because triangle angles are
bounded, and edge lengths are bounded by the local feature size. Consider the
edge $e_{i}=\overline{p_{j}p_{k}}$ common to $f_{i}$ and $t_{ijk}$ and let
$\alpha_{s}$ and $\alpha_{p}$ be the altitudes of $e_{i}$ in $f_{i}$ and
$t_{ijk}$, respectively. It follows that $A_{i}/A_{0}=\alpha_{s}/\alpha_{p}$.
Note $\alpha_{s}$ is less than the length of the longest edge of $f_{i}$.

Hence, assuming that $\textrm{lfs}(p_{j})\geq\textrm{lfs}(p_{k})$, we get that
$\alpha_{s}\leq\delta\textrm{lfs}(p_{j})$. On the other hand, the sparsity
condition guarantees
$\textbf{d}(p_{j},p_{k})\geq\sigma\epsilon\textrm{lfs}(p_{j})$, allowing us to
rewrite $\alpha_{s}\leq\frac{\delta}{\sigma\epsilon}\textbf{d}(p_{j},p_{k})$.
From 5.1, we have that
$\alpha_{p}\geq\textbf{d}(p_{j},p_{k})/(4\overline{\varrho}_{f}$). It follows
that $A_{i}/A_{0}\leq\frac{1}{2\sigma\overline{\varrho}_{f}}$. The proof
follows by invoking 1 to bound $H\geq\hat{h}_{s}\delta\textrm{lfs}(p_{i})$.

###  B.2. Octree refinement and outradii

Towards bounding the aspect ratio of Voronoi cells, we begin by proving some
basic properties of the octree described in Section 5. Given an octree box
$\square_{i}$, denote by $c_{i}$ its center and $r_{i}$ its radius (half its
diagonal length). Assume that the input $P$ has been scaled and shifted to fit
into the unit cube $[0,1]^{3}$. Starting with the unit cube as the box
associated with the root node of the octree, the refinement process terminates
with $r_{i}\leq\delta\textrm{lfs}(c_{i})$ for all leaf boxes $\square_{i}$.
Note that refinement depends only on lfs and is independent of the number of
points in $P$, and the distances between them. We establish the following
Lipschitz-like properties for the size of leaf boxes.

######  Claim 2.

If $\square_{i}$ is a leaf box, then
$\frac{\delta}{2+\delta}\textrm{lfs}(c_{i})\leq
r_{i}\leq\delta\textrm{lfs}(c_{i})$.

######  Proof B.4.

By definition the leaf box was not split, so
$r_{i}\leq\delta\textrm{lfs}(c_{i}).$ Letting $\square_{j}$ be the parent of
$\square_{i}$, it is clear that $\square_{j}$ had to be split. Hence,
$r_{j}=2r_{i}>\delta\textrm{lfs}(c_{j})$. By Lipschitzness,
$\textrm{lfs}(c_{i})\leq\textrm{lfs}(c_{j})+r_{i}\leq r_{i}(1+2/\delta)$.

######  Claim 3.

For any $p\in\square_{i}$, where $\square_{i}$ is a leaf box,
$\frac{\delta}{2(1+\delta)}\leq
r_{i}\leq\frac{\delta}{1-\delta}\textrm{lfs}(p)$.

######  Proof B.5.

Observe that $\textbf{d}(p,c_{i})\leq r_{i}$, so $\textrm{lfs}(p)$ is bounded
in terms of $\textrm{lfs}(c_{i})$. Conveniently, 2 bounds
$\textrm{lfs}(c_{i})$ in terms of $r_{i}$. To get the lower bound, we write
$\textrm{lfs}(p)\leq\textrm{lfs}(c_{i})+r_{i}\leq(\frac{2+\delta}{\delta}+1)r_{i}$.
For the upper bound, we write
$\textrm{lfs}(p)\geq\textrm{lfs}(c_{i})-r_{i}\geq(1/\delta-1)r_{i}$.

######  Lemma 4.

If $\square_{i}$ and $\square_{j}$ are two leaf boxes sharing a corner, then
$r_{i}/r_{j}\in[1/2,2]$.

######  Proof B.6.

Assume that $r_{j}\leq r_{i}$. From 2 we have
$r_{i}\leq\delta\textrm{lfs}(c_{i})$ and
$r_{j}\geq\frac{\delta}{2+\delta}\textrm{lfs}(c_{j})$. Together with lfs being
1-Lipschitz, this gives
$r_{j}\geq\frac{\delta}{2+\delta}\big{(}\textrm{lfs}(c_{i})-(r_{i}+r_{j})\big{)}\geq\frac{\delta}{2+\delta}(r_{i}/\delta-
r_{i}-r_{j}).$ Simplifying, we get
$r_{j}\geq\frac{r_{i}}{2}\frac{1-\delta}{1+\delta}.$ For $\delta<1/3$, we
obtain $r_{j}>r_{i}/4$. As the ratio of box radii is a power of two,
$r_{j}\in\\{r_{i}/2,r_{i}\\}$.

These propoerties of the octree may be used to bound the outradius of Voronoi
cells.

######  Lemma 5.

The Voronoi cell of $s\in\mathcal{S}$ has outradius at most
$\frac{2\delta}{1-3\delta}\textrm{lfs}(s)\leq\frac{4(1+\delta)}{1-3\delta}r_{i}$,
where $\square_{i}$ is the leaf box containing $s$.

######  Proof B.7.

Let $v$ be a vertex on the Voronoi cell of $s$. The octree construction
guarantees $v\in\square_{j}$, for some leaf box $\square_{j}$. 3 gives
$r_{j}\leq\delta/(1-\delta)\textrm{lfs}(v).$ Fixing some
$s^{\prime}\in\square_{j}\cap\mathcal{S}\neq\emptyset$, it follows that
$\textbf{d}(v,s)\leq\textbf{d}(v,s^{\prime})\leq 2r_{j}$. Hence,
$\textrm{lfs}(v)\geq\frac{1-\delta}{2\delta}\textbf{d}(v,s)$. By
Lipschitzness,
$\textrm{lfs}(s)\geq\textrm{lfs}(v)-\textbf{d}(v,s)\geq\frac{1-3\delta}{2\delta}\textbf{d}(v,s).$
As $s\in\square_{i}$, 3 gives
$\textrm{lfs}(s)\leq\frac{2(1+\delta)}{\delta}r_{i}$. It follows that
$\textbf{d}(v,s)\leq\frac{2\delta}{1-3\delta}\textrm{lfs}(s)\leq\frac{4(1+\delta)}{1-3\delta}r_{i}$.

###  B.3. Aspect ratio and size bounds

Any Voronoi vertex is in some box, and every box has at least one seed. This
provides an upper bound on the distance between a Voronoi vertex and its
closest seed, and an upper bound on the cell outradius, for both interior and
guide seeds. Interior seeds are at the center of a box containing no other
seeds, so interior cell inradius is at least a constant factor times $r$.
Combining the outradius and inradius bounds provides the following results.

See 5.3

######  Proof B.8.

Let $s\in\mathcal{S}$ be an interior seed and recall that $s$ was inserted at
the center of some empty leaf box $\square_{i}$. By construction, $s$ is the
only seed in $\square_{i}$. It follows that the inradius of $\textrm{Vor}(s)$
is at least $\frac{1}{2\sqrt{3}}r_{i}$, which is half the distance from
$c_{i}$ to any of its sides. The proof follows from the bound on the outradius
in terms of $r_{i}$ as provided by 5.

See 5.4

######  Proof B.9.

Let $s\equiv s_{ijk}\in\mathcal{S}$ be a boundary seed and recall the lower
bound of $\varrho_{v}\epsilon\textrm{lfs}(p_{i})$ on the inradius of
$\textrm{Vor}(s)$ from 5.2. By Lipschitzness, we may express this as
$\varrho_{v}\delta(1-\delta)\textrm{lfs}(s)$. On the other hand, an upper
bound of $\frac{4(1+\delta)}{1-3\delta}r_{a}$ on the circumradius of
$\textrm{Vor}(s)$ is provided by 5, where $\square_{a}$ is the leaf box
containing $s$. From 3, we have that
$r_{a}\leq\frac{\delta}{1-\delta}\textrm{lfs}(s)$. With both bounds expressed
in terms of $\textrm{lfs}(s)$, we evaluate their ratio.

See 5.5

######  Proof B.10.

Let
$\mathcal{I}=\mathcal{S}^{\downarrow}\cup\mathcal{S}^{\downarrow\downarrow}$
and $V(s)$ denote the Voronoi cell of seed $s$. Since the Voronoi cells of
interior seeds in $\mathcal{I}$ partition the volume $\mathcal{O}$,
$\int_{\mathcal{O}}\textrm{lfs}^{-3}=\sum_{s\in\mathcal{I}}\int_{V(s)}\textrm{lfs}^{-3}.$
Bounded outradii and inradii will bound each integral by as follows.

Fix a seed $s$ and let $R_{s}$ and $r_{s}$ be the circumradius and inradius of
$V(s)$, respectively. From 5, we have
$R\leq\frac{2\delta}{1-3\delta}\textrm{lfs}(s)$. By Lipschitzness, for any
$x\in\textrm{Vor}(s)$,
$\textrm{lfs}(x)\geq\frac{1-5\delta}{1-3\delta}\textrm{lfs}(s)$. Thus,
$\int_{\textrm{Vor}(s)}\textrm{lfs}^{-3}\geq
f_{1}(\delta)\textrm{lfs}^{-3}(s)\textrm{vol}{(\textrm{Vor}(s))}$, where
$f_{1}(\delta)=\big{(}\frac{1-3\delta}{1-5\delta}\big{)}^{3}$.

If $s\in\mathcal{S}^{\downarrow\downarrow}$, 3 yields
$r_{s}\geq\frac{\delta}{4\sqrt{3}(1+\delta)}\textrm{lfs}(s)$. Hence,
$\textrm{vol}({\textrm{Vor}(s)})\geq f_{2}(\delta)\textrm{lfs}^{3}(s)$, where
$f_{2}(\delta)=\frac{4\pi}{3}\left(\frac{\delta}{4\sqrt{3}(1+\delta)}\right)^{3}$.
If $s=s_{ijk}\in\mathcal{S}^{\downarrow}$, 5.2 gives
$r_{s}\geq\varrho_{v}\epsilon\textrm{lfs}(p_{i})$. Recalling
$\textbf{d}(p_{i},s_{ijk})=\delta\textrm{lfs}(p_{i})$ and the extension of lfs
to the interior of $\mathcal{O}$, we get
$\textrm{lfs}(s)\leq(1+\delta)\textrm{lfs}(p_{i})$. It follows that
$r_{s}\geq\frac{\varrho_{v}\delta}{1+\delta}\textrm{lfs}(s)$ and
$\textrm{vol}({\textrm{Vor}(s)})\geq f_{3}(\delta)\textrm{lfs}^{3}(s)$, where
$f_{3}(\delta)=\frac{4\pi}{3}\left(\frac{\varrho_{v}\delta}{1+\delta}\right)^{3}.$

Letting $f_{4}(\delta)=f_{1}(\delta)\cdot\min(f_{2}(\delta),f_{3}(\delta))$,
we established that $\textrm{vol}({\textrm{Vor}(s)})\geq
f_{4}(\delta)\textrm{lfs}^{3}(s)$. Plugging that into the above bound, we get
$\int_{\textrm{Vor}(s)}\textrm{lfs}^{-3}\geq f_{4}(\delta)$. Hence,
$\int_{\mathcal{O}}\textrm{lfs}^{-3}\geq f_{4}(\delta)|\mathcal{I}|\geq
f_{4}(\delta)|\mathcal{S}^{\downarrow\downarrow}|$. The proof follows by
observing that $\frac{1}{f_{4}(\delta)}\leq 18\sqrt{3}/\pi\cdot\epsilon^{-3}$.