Optimality of the Delaunay triangulation in ℝ d

In this paper we present new optimality results for the Delaunay triangulation of a set of points in ℝ ^d . These new results are true in all dimensionsd. In particular, we define a power function for a triangulation and show that the Delaunay triangulation minimizes the power function over all triangulations of a point set. We use this result to show that (a) the maximum min-containment radius (the radius of the smallest sphere containing the simplex) of the Delaunay triangulation of a point set in ℝ ^d is less than or equal to the maximum min-containment radius of any other triangulation of the point set, (b) the union of circumballs of triangles incident on an interior point in the Delaunay triangulation of a point set lies inside the union of the circumballs of triangles incident on the same point in any other triangulation of the point set, and (c) the weighted sum of squares of the edge lengths is the smallest for Delaunay triangulation, where the weight is the sum of volumes of the triangles incident on the edge. In addition we show that if a triangulation consists of only self-centered triangles (a simplex whose circumcenter falls inside the simplex), then it is the Delaunay triangulation.     

Delaunay Triangulation of Manifolds

We present an algorithm for producing Delaunay triangulations of manifolds. The algorithm can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. Given a set of sample points and an atlas on a compact manifold, a manifold Delaunay complex is produced for a perturbed point set provided the transition functions are bi-Lipschitz with a constant close to 1, and the original sample points meet a local density requirement; no smoothness assumptions are required. If the transition functions are smooth, the output is a triangulation of the manifold. The output complex is naturally endowed with a piecewise-flat metric which, when the original manifold is Riemannian, is a close approximation of the original Riemannian metric. In this case the output complex is also a Delaunay triangulation of its vertices with respect to this piecewise-flat metric.     

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.     

Perturbations for Delaunay and weighted Delaunay 3D triangulations

The Delaunay triangulation and the weighted Delaunay triangulation are not uniquely defined when the input set is degenerate. We present a new symbolic perturbation that allows to always define these triangulations in a unique way, as soon as the points are not all coplanar. No flat tetrahedron exists in the defined triangulation. The perturbation scheme is easy to code. It is implemented in cgal, and guarantees that both vertex insertion and vertex removal are fully robust.     

Efficiently updating constrained Delaunay triangulations

TheConstrained Delaunay Triangulation of a set of obstacle line segments in the plane is the Delaunay triangulation of the endpoint set of these obstacles with the restriction that the edge set of the triangulation contains all these obstacles. In this paper we present an optimal (logn +k) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set ofn obstacle line segments in the plane. Herek is the number of Delaunay edges deleted and added in the triangulation during the updates.This work is supported by NSERC grant OPG0041629.     

A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in <Emphasis Type="Italic">ℜ</Emphasis><Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a heuristic for the Euclidean Steiner tree problem in ℜ ^d for d≥2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in ℜ ^d for 2≤d≤5.     

Delaunay Refinement for Piecewise Smooth Complexes

We present a Delaunay refinement algorithm for meshing a piecewise smooth complex in three dimensions. The algorithm protects edges with weighted points to avoid the difficulty posed by small angles between adjacent input elements. These weights are chosen to mimic the local feature size and to satisfy a Lipschitz-like property. A Delaunay refinement algorithm using the weighted Voronoi diagram is shown to terminate with the recovery of the topology of the input. Guaranteed bounds on the aspect ratios, normal variation, and dihedral angles are also provided. To this end, we present new concepts and results including a new definition of local feature size and a proof for a generalized topological ball property.     

Reconstruction Using Witness Complexes

We present a novel reconstruction algorithm that, given an input point set sampled from an object S, builds a one-parameter family of complexes that approximate S at different scales. At a high level, our method is very similar in spirit to Chew’s surface meshing algorithm, with one notable difference though: the restricted Delaunay triangulation is replaced by the witness complex, which makes our algorithm applicable in any metric space. To prove its correctness on curves and surfaces, we highlight the relationship between the witness complex and the restricted Delaunay triangulation in 2d and in 3d. Specifically, we prove that both complexes are equal in 2d and closely related in 3d, under some mild sampling assumptions.     

Delaunay triangulations approximate anchor hulls

Recent results establish that a subset of the Voronoi diagram of a point set that is sampled from the smooth boundary of a shape approximates the medial axis. The corresponding question for the dual Delaunay triangulation is not addressed in the literature. We show that, for two-dimensional shapes, the Delaunay triangulation approximates a specific structure which we call anchor hulls. As an application we demonstrate that our approximation result is useful for the problem of shape matching.     

A Discrete Laplace–Beltrami Operator for Simplicial Surfaces

We define a discrete Laplace–Beltrami operator for simplicial surfaces (Definition 16). It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the well known finite-elements Laplacian (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic functions, discrete mean curvature, and discrete minimal surfaces. The definition of the discrete Laplace–Beltrami operator depends on the existence and uniqueness of Delaunay tessellations in piecewise flat surfaces. While the existence is known, we prove the uniqueness. Using Rippa’s Theorem we show that, as claimed, Musin’s harmonic index provides an optimality criterion for Delaunay triangulations, and this can be used to prove that the edge flipping algorithm terminates also in the setting of piecewise flat surfaces. Research for this article was supported by the DFG Research Unit 565 “Polyhedral Surfaces” and the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

Nice Point Sets Can Have Nasty Delaunay Triangulations

   Abstract. We consider the complexity of Delaunay triangulations of sets of points in R ³ under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R ³ with spread Δ has complexity Ω(min{ Δ³, nΔ, n² }) and O(min{ Δ⁴, n ² }). For the case

Maillage simplicial d'un polyèdre arbitraire

Issues related to the existence of a triangulation of an arbitrary polyhedron are addressed. Given a boundary surface mesh (a set of triangular facets), the problem to decide whether or not a triangulation (with no internal points apart from the Steiner points) exists is reported to be NP-hard. In this paper, an algorithm to triangulate a general polyhedron is used which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning and a final phase that makes it possible to remove the additional (non-Steiner) points previously defined so as to recover the initial boundary mesh thus resulting in a mesh of the given polyhedron. To cite this article: P.-L. George, H. Borouchaki, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

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.     

The Delaunay triangulation for multidimensional surfaces and its approximative properties

We define the Delaunay triangulation for surfaces and prove an analog of the G. Voronoi empty sphere theorem. We also prove a convergence theorem for gradients of piecewise linear approximations constructed on the Delaunay triangulation for functions differentiable on smooth surfaces.     

Dense Point Sets Have Sparse Delaunay Triangulations or “... But Not Too Nasty”

The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of $n$ points in~$\Real^3$ with spread $\Delta$ has complexity $O(\Delta^3)$. This bound is tight in the worst case for all $\Delta = O(\sqrt{n})$. In particular, the Delaunay triangulation of any dense point set has linear complexity. We also generalize this upper bound to regular triangulations of $k$-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any $n$ and $\Delta = O(n)$, we construct a regular triangulation of complexity $\Omega(n\Delta)$ whose $n$ vertices have spread $\Delta$.     

Dirichlet problem for semilinear edge-degenerate elliptic equations with singular potential term

In this paper, we introduce weighted p-Sobolev spaces on manifolds with edge singularities. We give the proof for the corresponding edge type Sobolev inequality, Poincaré inequality and Hardy inequality. As an application of these inequalities, we prove the existence of nontrivial weak solutions for the Dirichlet problem of semilinear elliptic equations with singular potentials on manifolds with edge singularities.     

基于Delaunay三角剖分的地表平均温度模拟

利用Delaunay三角网对目标区域进行剖分,在对地表温度进行高度插值后,运用二重积分的思想建立了基于Delaunayr三角剖分的地表平均温度测量模型.同时以南极地表平均温度的测量为例,将67个自动气象地表台站、46个气象地表台站以及56个高空气象观测站的加权平均温度与地表平均温度的数据进行分析,得到南极2015全年地表平均温度均在-8℃以下,最低温约为-20℃,符合南极大陆地表温度的实际情况.     

Existence and regularity for generalised harmonic maps associated to a nonlocal polyconvex energy of Skyrme type

We prove existence and regularity of critical points of arbitrary degree for a generalised harmonic map problem, in which there is an additional nonlocal polyconvex term in the energy, heuristically of the same order as the Dirichlet term. The proof of regularity hinges upon a special nonlinear structure in the Euler–Lagrange equation similar to that possessed by the harmonic map equation. The functional is of a type appearing in certain models of the quantum Hall effect describing nonlocal Skyrmions.     

Optimal Delaunay Triangulations

The Delaunay triangulation, in both classic and more generalized sense, is studied in this paper for minimizing the linear interpolation error (measure in L^P-norm) for a given function. The classic Delaunay triangulation can then be characterized as an optimal triangulation that minimizes the interpolation error for the isotropic function ‖x‖^2 among all the triangulations with a given set of vertices. For a more general function, a functiondependent Delaunay triangulation is then defined to be an optimal triangulation that minimizes the interpolation error for this function and its construction can be obtained by a simple lifting and projection procedure. The optimal Delaunay triangulation is the one that minimizes the interpolation error among all triangulations with the same number of vertices, i.e. the distribution of vertices are optimized in order to minimize the interpolation error. Such a function-depend entoptimal Delaunay triangulation is proved to exist for any given convex continuous function.On an optimal Delaunay triangulation associated with f, it is proved that △↓f at the interior vertices can be exactly recovered by the function values on its neighboring vertices.Since the optimal Delaunay triangulation is difficult to obtain in practice, the concept of nearly optimal triangulation is introduced and two sufficient conditions are presented for a triangulation to be nearly optimal.