## Practical Delaunay triangulation algorithms for surface reconstruction and related problems

##### Abstract

The Delaunay triangulation is one of the fundamental problems in computational
geometry, dual to the well-known Voronoi diagram. It has numerous applications
in various disciplines such as computer graphics, computer vision, and robotics.
This thesis deals with a number of interrelated questions arising in modeling shapes
by computing Delaunay triangulations. We give algorithms for surface reconstruction,
computing Delaunay triangulations given surfaces, and computing Delaunay
triangulations in general.
Given a set of samples from a surface, the surface reconstruction problem is
to construct a piecewise linear approximation of the original surface. We give two
surface reconstruction algorithms with guarantees of both geometric and topological
correctness using the 3D Delaunay triangulation of the input samples. The first
algorithm selects a set of Delaunay triangles using a simple geometric test and
extracts a manifold from it. It is the first surface reconstruction algorithm with
topological guarantee of correctness. The second algorithm improves the robustness
using the weighted Voronoi diagrams called power diagram.
When the surface on which the samples lie are known, we can use the connectivity
of the surface to speed up the Delaunay triangulation. We give an O(n log∗ n)
expected time algorithm to compute the 3D Delaunay triangulation given the surface
on which the samples lie, under some realistic assumptions. It improves upon
O(n log n) expected time usual randomized incremental algorithm in this case. The
algorithm can be useful for mesh generation and medial axis construction.
The randomized incremental algorithm for Delaunay triangulation is theoretically
optimal in expected time but suffers from serious thrashing because of its
random memory access pattern when the data structure gets too large to fit in
memory. We propose a new insertion order called biased randomized insertion order
(BRIO) which removes enough randomness to significantly improve performance,
but leaves enough randomness so that the algorithm remains theoretically optimal.
We show by experiments that the size of input data we can compute in a given
machine increases dramatically using BRIO instead of the total random order.