Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces

It is well known that the complexity of the Delaunay triangulation of $n$ points in $\RR ^d$, i.e., the number of its simplices, can be $\Omega (n^{\lceil {d}/{2}\rceil })$. In particular, in $\RR ^3$, the number of tetrahedra can be quadratic. Put another way, if the points are uniformly distributed in a cube or a ball, the expected complexity of the Delaunay triangulation is only linear. The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface. In this paper we bound the complexity of the Delaunay triangulation of points distributed on the boundary of a given polyhedron. Under a mild uniform sampling condition, we provide deterministic asymptotic bounds on the complexity of the three-dimensional Delaunay triangulation of the points when the sampling density increases. More precisely, we show that the complexity is $O(n^{1.8})$ for general polyhedral surfaces and $O(n\sqrt{n})$ for convex polyhedral surfaces. Our proof uses a geometric result of independent interest that states that the medial axis of a surface is well approximated by a subset of the Voronoi vertices of the sample points.     

Triangulations in CGAL

This paper presents the main algorithmic and design choices that have been made to implement triangulations in the computational geometry algorithms library .     

Isotopic Implicit Surface Meshing

This paper addresses the problem of piecewise linear approximation of implicit surfaces. We first give a criterion ensuring that the zero-set of a smooth function and the one of a piecewise linear approximation of it are isotopic. Then, we deduce from this criterion an implicit surface meshing algorithm certifying that the output mesh is isotopic to the actual implicit surface. This is the first algorithm achieving this goal in a provably correct way.     

Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling conditions. In this paper, we prove that these results do not extend to higher-dimensional manifolds, even under strong sampling conditions such as uniform point density. On the positive side, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between restricted Delaunay triangulation and witness complex hold on higher-dimensional manifolds as well. We derive from our structural results an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample to be sparse. Its running time is bounded by c(d)n ², where n is the size of the input point cloud, and c(d) is a constant depending solely (yet exponentially) on the dimension d of the ambient space. Although this running time makes our reconstruction algorithm rather theoretical, recent work has shown that a variant of our approach can be made tractable in arbitrary dimensions, by building upon the results of this paper. This work was done while S.Y. Oudot was a post-doctoral fellow at Stanford University. His email there is no longer valid.     

Assembly of the Entire Carbon Backbone of a Stereoisomer of the Antitumor Marine Natural Product Hemicalide

A strategy for the assembly of the entire carbon backbone of a stereoisomer of the antitumor marine natural product hemicalide has been investigated. The devised convergent approach relies on Horner–Wadsworth–Emmons and Julia–Kocienski olefination reactions for the construction of the C6=C7 and C34=C35 double bonds, respectively, an aldol reaction to create the C27−C28 bond, and a Suzuki–Miyaura cross-coupling as the endgame to form the C15−C16 bond.     

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in R ^d , the maximum complexity of its Voronoi diagram under the L _∞ metric, and also under a simplicial distance function, are both shown to be . The upper bound for the case of the L _∞ metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R ^d . This complexity is , for d ≥ 1 , and it improves to , for d ≥ 2 , if all the hypercubes have the same size. Under the L ₁ metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R ³ is shown to be . We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R ^d under a simplicial or L _∞ distance function. Their expected randomized complexities are for simplicial diagrams and for L _∞ -diagrams. Received July 31, 1995, and in revised form September 9, 1997.     

Triangulating Smooth Submanifolds with Light Scaffolding

We propose an algorithm to sample and mesh a k-submanifold M{\mathcal{M}} of positive reach embedded in \mathbbR^d{\mathbb{R}^{d}} . The algorithm first constructs a crude sample of M{\mathcal{M}} . It then refines the sample according to a prescribed parameter e{\varepsilon} , and builds a mesh that approximates M{\mathcal{M}} . Differently from most algorithms that have been developed for meshing surfaces of \mathbbR ³{\mathbb{R} ^3} , the refinement phase does not rely on a subdivision of \mathbbR ^d{\mathbb{R} ^d} (such as a grid or a triangulation of the sample points) since the size of such scaffoldings depends exponentially on the ambient dimension d. Instead, we only compute local stars consisting of k-dimensional simplices around each sample point. By refining the sample, we can ensure that all stars become coherent leading to a k-dimensional triangulated manifold [^(M)]{\hat{\mathcal{M}}} . The algorithm uses only simple numerical operations. We show that the size of the sample is O(e^-k){O(\varepsilon ^{-k})} and that [^(M)]{\hat{\mathcal{M}}} is a good triangulation of M{\mathcal{M}} . More specifically, we show that M{\mathcal{M}} and [^(M)]{\hat{\mathcal{M}}} are isotopic, that their Hausdorff distance is O(e²){O(\varepsilon ^{2})} and that the maximum angle between their tangent bundles is O(e){O(\varepsilon )} . The asymptotic complexity of the algorithm is T(e) = O(e^-k2-k){T(\varepsilon) = O(\varepsilon ^{-k^2-k})} (for fixed M, d{\mathcal{M}, d} and k).     

Bregman Voronoi Diagrams

The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define various variants of Voronoi diagrams depending on the class of objects, the distance function and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow one to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g., k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connection with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation.     

A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces

Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the complexity of the Delaunay triangulation of points in R³ may be quadratic in the worst case, we show in this paper that it is only linear when the points are distributed on a fixed set of well-sampled facets of R³ (e.g. the planar polygons in a polyhedron). Our bound is deterministic and the constants are explicitly given.