Abstract:
This article presents the formal proof of correctness for a plane Delaunay triangulation algorithm. It consists in repeating a sequence of edge flippings from an initial triangulation until the Delaunay property is achieved. To describe triangulations, we rely on a combinatorial hypermap specification framework we have been developing for years. We embed hypermaps in the plane by attaching coordinates to elements in a consistent way. We then describe what are legal and illegal Delaunay edges and a flipping operation which we show preserves hypermap, triangulation, and embedding invariants. To prove the termination of the algorithm, we use a generic approach expressing that any non-cyclic relation is well-founded when working on a finite set.

Abstract:
We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.

Abstract:
A graph based algorithm for generating the Delaunay triangulation of a planar point set is presented in this paper. The first step is to calculate the Euclidean Minimum Spanning Tree (EMST) of the given points. The EMST is then augumented to triangle mesh. Finally the Delaunay Triangulation of the given points is obtained by local tranformation acording to Max Min angle criteria. The concepts and properties of Voronoi diagram of a planar point set are slso discussed in the paper.

Abstract:
A graph based algorithm for generating the delaunay triangulation of a point set within an arbitrary 2D domain (denoted as DTAD for short) is presented in this paper. The basic idea is to calculate the CMST(constrained minimum spanning tree) of the given points within an arbitrary 2D domain. The CMST is then augmented to triangle mesh. Finally the DTAD is obtained by local optimal transformation. The actual application of the algorithm in the automatic finite element mesh generation is also shown in the paper.

Abstract:
We present a new and simple randomized algorithm for constructing the Delaunay triangulation using nearest neighbor graphs for point location. Under suitable assumptions, it runs in linear expected time for points in the plane with polynomially bounded spread, i.e., if the ratio between the largest and smallest pointwise distance is polynomially bounded. This also holds for point sets with bounded spread in higher dimensions as long as the expected complexity of the Delaunay triangulation of a sample of the points is linear in the sample size.

Abstract:
According to the characteristics of uniqueness and best of Delaunay triangulation, actualized algorithm to given arbitrary plane polygons used by Delaunay triangulation is expatiated in details. And the correlative pretreatment technology of arbitrary plane polygons is introduced. At last, this algorithm is improved in two aspects and an example of Delaunay triangulation is furnished.

Abstract:
We describe a randomized algorithm that, given a set $P$ of points in the plane, computes the best location to insert a new point $p$, such that the Delaunay triangulation of $P\cup\{p\}$ has the largest possible minimum angle. The expected running time of our algorithm is at most cubic, improving the roughly quartic time of the best previously known algorithm. It slows down to slightly super-cubic if we also specify a set of non-crossing segments with endpoints in $P$ and insist that the triangulation respect these segments, i.e., is the constrained Delaunay triangulation of the points and segments.

Abstract:
In the study of depth functions it is important to decide whether we want such a function to be sensitive to multimodality or not. In this paper we analyze the Delaunay depth function, which is sensitive to multimodality and compare this depth with others, as convex depth and location depth. We study the stratification that Delaunay depth induces in the point set (layers) and in the whole plane (levels), and we develop an algorithm for computing the Delaunay depth contours, associated to a point set in the plane, with running time O(n log^2 n). The depth of a query point p with respect to a data set S in the plane is the depth of p in the union of S and p. When S and p are given in the input the Delaunay depth can be computed in O(n log n), and we prove that this value is optimal.

Abstract:
Let $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $\frac{4 \pi \sqrt{3}}{9}$-spanner of the unit-disk graph $\UDG(V)$. This algorithm makes only one round of communication and each point of $V$ broadcasts at most 5 messages. This improves the previously best message-bound of 11 by Ara\'{u}jo and Rodrigues (Fast localized Delaunay triangulation, Lecture Notes in Computer Science, volume 3544, 2004).

Abstract:
Terrain landform features play major roles in such fields as geomorphology type recognition, relief map generalization, DEM construction and hydrology analysis. This paper presents an automatic method to extract terrain landform features and organize drainage system into tree structure based on bend assessment using Delaunay triangulation model. Compared with traditional DEM or TIN based methods, this pure vector approach obtains not only the topological structure of drainage system in planar graph, but also the valley distribution polygon range. Depending on geometrical computation and judgment of vector line, polygon, the structured properties in drainage representation is enhanced, avoiding the case of noise disturbance in DEM based method. The core algorithm makes use of the ability of Delaunay triangulation in detecting hierarchical structure of each contour line. Three kinds of tree structure organization are discussed: the hierarchical binary tree representing bend inclusion relationship contained in single contour line, the plane structure tree representing valley topological relationship, the semantic hierarchical tree representing valley join level from the point of view of hydrology. This paper gives systemically experiment and detailed comparative analysis.