Search

Given a triangulation of a point set on the plane, dilation of any pair of the points is the ratio of their shortest path length to their Euclidean distance. The maximum dilation over all pairs of points is called the dilation of this triangulation. Minimum dilation triangulation problem seeks a triangulation with the least possible dilation of an input point set. For this problem no polynomial time algorithm is known. We present an exact algorithm based on a branch and bound method for finding minimum dilation triangulations. This deterministic algorithm after generating an initial solution, iteratively computes a lower bound for the answer and then applies a branch and bound method to find a better solution. It also uses a local search method to improve the initial solution and the obtained solution of the branch and bound method. We implemented our algorithm and conducted computational experiments on some benchmark instances. The efficacy of the approach is demonstrated by comparing its results with two other published methods.

In this paper, we propose a new graphics processing unit GPU method able to compute the 2D constrained Delaunay triangulation CDT of a planar straight-line graph consisting of points and segments. All existing methods compute the Delaunay triangulation of the given point set, insert all the segments, and then finally transform the resulting triangulation into the CDT. To the contrary, our novel approach simultaneously inserts points and segments into the triangulation, taking special care to avoid conflicts during retriangulations due to concurrent insertion of points or concurrent edge flips. Our implementation using the Compute Unified Device Architecture programming model on NVIDIA GPUs improves, in terms of running time, the best known GPU-based approach to the CDT problem.

This paper aims to locate $p$ resources in a nonconvex demand plane having $n $demand points. The objective of the location problem is to find the location for these $p$ resources so that the distance from each of $n$ demand points to its nearest resource is minimized, thus simulating a $p$-center problem. We employ various geometrical structures for solving this location problem. The suggested approach is also capable of finding the optimal value of $p$ so that all demand points have at least one resource at a distance $\Delta $, where $\Delta $ is the maximum permissible distance for emergency services. Finally, an implementation of the proposed approach is presented and it is observed that the suggested approach rapidly converges towards the optimal location.

In this paper we show that most sequential randomized incremental algorithms are in fact parallel. We consider several random incremental algorithms including algorithms for comparison sorting and Delaunay triangulation; linear programming, closest pair, and smallest enclosing disk in constant dimensions; as well as least-element lists and strongly connected components on graphs.We analyze the dependence between iterations in an algorithm, and show that the dependence structure is shallow for all of the algorithms, implying high parallelism. We identify three types of dependences found in the algorithms studied and present a framework for analyzing each type of algorithm. Using the framework gives work-efficient polylogarithmic-depth parallel algorithms for most of the problems that we study. Some of these algorithms are straightforward (e.g., sorting and linear programming), while others are more novel and require more effort to obtain the desired bounds (e.g., Delaunay triangulation and strongly connected components). The most surprising of these results is for planar Delaunay triangulation for which the incremental approach is by far the most commonly used in practice, but for which it was not previously known whether it is theoretically efficient in parallel.

We introduce Recursive Spoke Darts (RSD): a recursive hyperplane sampling algorithm that exploits the full duality between Voronoi and Delaunay entities of various dimensions. Our algorithm abandons the dependence on the empty sphere principle in the generation of Delaunay simplices providing the foundation needed for scalable consistent meshing. The algorithm relies on two simple operations: line-hyperplane trimming and spherical range search. Consequently, this approach improves scalability as multiple processors can operate on different seeds at the same time. Moreover, generating consistent meshes across processors eliminates the communication needed between them, improving scalability even more. We introduce a simple tweak to the algo- rithm which makes it possible not to visit all vertices of a Voronoi cell, generating almost-exact Delaunay graphs while avoiding the natural curse of dimensionality in high dimensions.

On the basis of the assumptions it can be concluded that customers in the selected area procure the nearest center. Each client within the Voronoi diagram cell is closest to the designated center than the other one. Polygons created by dividing differ from Polish administrative division. The Regions resulting from the Voronoi cell division of polish are convex polygons. Application of Delaunay triangulation divides a network into triangles with as little corners. The result of this procedure is to obtain a minimum distance between centroids. This reduces the transport time and minimizes the costs of delivery. In the work the aspects of client subjective assessment in making decisions about the choice of the distribution center has been omitted i.e. the price of the product, the quality of the offer or the actual transport.

Delaunay meshes (DM) are a special type of triangle mesh where the local Delaunay condition holds everywhere. We present an efficient algorithm to convert an arbitrary manifold triangle mesh M into a Delaunay mesh. We show that the constructed DM has O ( Kn ) vertices, where n is the number of vertices in M and K is a model-dependent constant. We also develop a novel algorithm to simplify Delaunay meshes, allowing a smooth choice of detail levels. Our methods are conceptually simple, theoretically sound and easy to implement. The DM construction algorithm also scales well due to its O ( nK log K ) time complexity. Delaunay meshes have many favorable geometric and numerical properties. For example, a DM has exactly the same geometry as the input mesh, and it can be encoded by any mesh data structure. Moreover, the empty geodesic circumcircle property implies that the commonly used cotangent Laplace-Beltrami operator has non-negative weights. Therefore, the existing digital geometry processing algorithms can benefit the numerical stability of DM without changing any codes. We observe that DMs can improve the accuracy of the heat method for computing geodesic distances. Also, popular parameterization techniques, such as discrete harmonic mapping, produce more stable results on the DMs than on the input meshes.

We prove that the dual of the digital Voronoi diagram constructed by flooding the plane from the data points gives a geometrically and topologically correct dual triangulation. This provides the proof of correctness for recently developed GPU algorithms that outperform traditional CPU algorithms for constructing two-dimensional Delaunay triangulations.

Delaunay triangulation is gradually playing an important role in the field of finite element analysis, image recognition, and medical visualization. Considering the quality and partition efficiency, a new Delaunay triangulation method based on constrained maximum circumscribed circle is proposed. First, according to two important criteria, the empty circle features and the maximized minimum angle characteristics, we established constrained conditions. Then, we iterated the container vertices, structure triangular face linked lists, and finally got the Delaunay data. The experimental results showed that the efficiency of the improved triangulation dissection method increased by 9.47% compared with traditional triangulation algorithms in irregular triangle vertex data.

Let P be a collection of n points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of O ( n 2+ϵ ), for any ϵ > 0, on the maximum number of discrete changes that the Delaunay triangulation DT( P ) of P experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.

A simple and flexible algorithm for finding zeros of a complex function is presented. An arbitrary-shaped search region can be considered and a very wide class of functions can be analyzed, including those containing singular points or even branch cuts. The proposed technique is based on sampling the function at nodes of a regular or a self-adaptive mesh and on the analysis of the function sign changes. As a result, a set of candidate points is created, where the signs of the real and imaginary parts of the function change simultaneously. To verify and refine the results, an iterative algorithm is applied. The validity of the presented technique is supported by the results obtained in numerical tests involving three different types of functions.

In this paper, we present a fully automatic Delaunay based sculpting algorithm for approximating the shape of a finite set of points S in R 2 . The algorithm generates a relaxed Gabriel graph ( R G G ) that consists of most of the Gabriel edges and a few non-Gabriel edges induced by the Delaunay triangulation. Holes are characterized through a structural pattern called as body-arm formed by the Delaunay triangles in the void regions. R G G is constructed through an iterative removal of Delaunay triangles subjected to circumcenter (of triangle) and topological regularity constraints in O ( n log n ) time using O ( n ) space. We introduce the notion of directed boundary samples which characterizes the two dimensional objects based on the alignment of their boundaries in the cavities. Theoretically, we justify our algorithm by showing that under given sampling conditions, the boundary of R G G captures the topological properties of objects having directed boundary samples. Unlike many other approaches, our algorithm does not require tuning of any external parameter to approximate the geometric shape of point set and hence human intervention is completely eliminated. Experimental evaluations of the proposed technique are done using L 2 error norm measure, which is the symmetric difference between the boundaries of reconstructed shape and the original shape. We demonstrate the efficacy of our automatic shape reconstruction technique by showing several examples and experiments with varying point set densities and distributions.

A fast unstructured mesh generation algorithm based on conforming centroidal Voronoi Delaunay triangulation (CfCVDT) algorithm (Ju, 2007) is proposed in this paper. In the new algorithm, the constrained Delaunay triangulation (CDT) algorithm is used only for the generation of the initial mesh. The mesh quality shall be continuously improved by updating the positions of vertices and flipping edges in a number of iterations. Since the most time consuming procedure in CfCVDT algorithm is the CDT in each iteration which has been successfully avoided in this new algorithm the efficiency has been significantly improved. Furthermore, the meshes generated by this algorithm have similar high quality features as that generated by CfCVDT. When complex interfaces are involved, our algorithm can keep the mesh conforming to the interfaces very efficiently. By using various density functions, this algorithm can produce high quality non-uniform meshes for potentially many applications. A fast high quality triangular mesh generation algorithm (FCfCVDT) is proposed based on the CfCVDT algorithm.The FCfCVDT algorithm significantly improves the efficiency of CfCVDT algorithm at the same time maintains the mesh quality.It is capable of generating high quality body/interface fitted meshes for complicate domains/interfaces.

In this paper, we examine relationship of graphs on surfaces: triangulations, quadrangulations and optimal $$1$$1-planar graphs. For a given quadrangulation $$G$$G of a closed surface $$F^2, G$$F2,G can be extended to a triangulation by adding a diagonal edge in every face of $$G$$G. We show that every quadrangulation of $$F^2$$F2 with at least six vertices can be extended to a $$4$$4-connected triangulation. Moreover, we show that every $$5$$5-connected triangulation of $$F^2$$F2 has a $$3$$3-connected spanning quadrangulation subgraph. As corollaries of these results, we show that every optimal $$1$$1-planar graph has a $$4$$4-connected triangulation subgraph, and that every plane $$5$$5-connected triangulation can be extended to an optimal $$1$$1-planar graph by adding some edges.

Anisotropic meshes are desirable for various applications, such as the numerical solving of partial differential equations and graphics.In this report, we introduce an algorithm to compute discrete approximations of Riemannian Voronoi diagrams on 2-manifolds.This is not straightforward because geodesics, shortest paths between points, and therefore distances cannot, in general, be computed exactly.We give conditions that guarantee that our discrete Riemannian Voronoi diagram is combinatorially equivalent to the exact Riemannian Voronoi diagram.This allows us to build upon recent theoretical results on Riemannian Delaunay triangulations, and guarantee that the dual of our discrete Riemannian Voronoi diagram is an embedded triangulation using both approximate geodesics and straight edges.Our implementation employs recent developments in the numerical computation of geodesic distances.We observe that, in practice, our discrete Voronoi Diagram is correct in a far wider range of settings than our theoretical bounds imply.Both the theoretical guarantees on the approximation of the Voronoi diagram and the implementation are new and provides a step towards the practical application of Riemannian Delaunay triangulations.; Les maillages anisotropes sont désirables pour de nombreuses applications, telles que la résolution numérique d'équations aux dérivées partielles ou la visualisation.Dans ce rapport, nous présentons un algorithme qui permet de calculer une approximation discrète d'un diagramme de Voronoi Riemannien sur une 2-variété.Il s'agit d'une tache complexe car ce diagramme est basé sur la notion de courbe géodésique, qui ne peut en général pas être calculée de manière exacte.Nous donnons dans ce rapport des conditions qui garantissent que notre diagramme de Voronoi Riemannien discret est combinatoirement équivalent au diagramme de Voronoi Riemannien exact.Ceci nous permet ensuite d'utiliser des résultats récents sur les triangulations de Delaunay Riemanniennes pour garantir le fait que le dual de notre diagramme de Voronoi Riemannien discret est une triangulation plongée, à la fois en utilisant des arêtes géodésiques et des arêtes droites.Notre implémentation est basée sur de récentes avancées dans le calcul numérique des distances géodésiques.Nous observons en pratique que notre diagramme de Voronoi Riemannien discret est correct dans des conditions beaucoup moins contraignantes que ce que notre théorie implique.Les garanties théoriques et l'approximation du diagramme de Voronoi sont nouvelles et sont une étape de plus vers une utilisation pratique des triangulations de Delaunay Riemanniennes.

A new edge-based partition for triangle meshes is presented, the Seven Triangle Quasi-Delaunay partition (7T-QD). The proposed partition joins together ideas of the Seven Triangle Longest-Edge partition (7T-LE), and the classical criteria for constructing Delaunay meshes. The new partition performs similarly compared to the Delaunay triangulation (7T-D) with the benefit of being more robust and with a cheaper cost in computation. It will be proved that in most of the cases the 7T-QD is equal to the 7T-D. In addition, numerical tests will show that the difference on the minimum angle obtained by the 7T-QD and by the 7T-D is negligible.

Starting with an ideal triangulation of M ∘ , the interior of a compact 3-manifold M with boundary, no component of which is a 2-sphere, we provide a construction, called an inflation of the ideal triangulation, to obtain a strongly related triangulation of M itself. Besides a step-by-step algorithm for such a construction, we provide examples of an inflation of the two-tetrahedra ideal triangulation of the complement of the figure-eight knot in S 3 , giving a minimal triangulation, having ten tetrahedra, of the figure-eight knot exterior. As another example, we provide an inflation of the one-tetrahedron Gieseking manifold giving a minimal triangulation, having seven tetrahedra, of a non-orientable compact 3-manifold with Klein bottle boundary. Several applications of inflations are discussed.

In view of the simplicity and the linearity of regular grid insertion, a multi-grid insertion scheme is proposed for the three-dimensional Delaunay triangulation of non-uniform point distributions by recursive application of the regular grid insertion to an arbitrary subset of the original point set. The fundamentals and difficulties of three-dimensional Delaunay triangulation of highly non-uniformly distributed points by the insertion method are reviewed. Current strategies and methods of point insertions for non-uniformly distributed spatial points are discussed. An enhanced kd-tree insertion algorithm with a specified number of points in a cell and its natural sequence derived from a sandwich insertion scheme is also presented. The regular grid insertion, the enhanced kd-tree insertion and the multi-grid insertion have been rigorously studied with benchmark non-uniform distributions of 0.4–20 million points. It is found that the kd-tree insertion is more efficient in locating the base tetrahedron, but it is also more sensitive to the triangulation of non-uniform point distributions with a large amount of conflicting elongated tetrahedra. Including the grid construction time, multi-grid insertion is the most stable and efficient for all the uniform and non-uniform point distributions tested.

Evaluation methods for the spatial distribution uniformity of a large number of particles have important applications in a range of scientific and industrial problems. We report a quantitative image-processing method to evaluate the spatial distribution uniformity of particles using the Voronoi tessellation and Delaunay triangulation. Given the geometric particle centroids, we constructed the Voronoi tessellation and Delaunay triangulation. For each of the Voronoi cell, the volume, facet area, and number of neighbors (facets) were calculated. For the Delaunay simplices, the volume and the distance between neighbors were calculated and the distributive characteristics were compared between different particle patterns. Simulation results demonstrated that distributions of the above metrics were numerically related to the uniformity of the particle spatial displacement. More studies are needed to further validate the results and refine the method.

This paper introduces a parameterization-based approach for anisotropic surface meshing. Given an input surface equipped with an arbitrary Riemannian metric, this method generates a metric-adapted mesh with user-specified number of vertices. In the proposed method, the edge length of the input surface is directly adjusted according to the given Riemannian metric at first. Then the adjusted surface is conformally embedded into a parametric 2D domain and a weighted Centroidal Voronoi Tessellation and its dual Delaunay triangulation are computed on the parametric domain. Finally the generated Delaunay triangulation can be mapped from the parametric domain to the original space, and the triangulation exhibits the desired anisotropic property. We compute the high-quality remeshing results for surfaces with different types of topologies and compare our method with several state-of-the-art approaches in anisotropic surface meshing by using the standard measurement criteria.

To increase the efficiency when processing large data sets, a novel parallel algorithm is proposed for constructing the Delaunay triangulation of a planar point set based on a twofold-divide-and-conquer scheme. This algorithm automatically divides the planar point set into several non-overlapping subsets along the x-axis and y-axis directions alternately, according to the number of points and their spatial distribution. Next, the Guibas–Stolfi divide-and-conquer algorithm is applied to construct Delaunay sub-triangulations in each subset. Finally, the sub-triangulations are merged based on the binary tree. All three sequential steps are processed using multitasking parallel technology. Our results show that the proposed parallel algorithm is efficient for constructing the Delaunay triangulation with a good speed-up.

New ideas are presented in this paper for the boundary recovery of 3D Delaunay triangulation. Fully constrained Delaunay triangulations in terms of geometrical and topological integrities on all boundary edges and facets are required in many applications, such as meshing by components, fluid–structure interactions, parallel mesh generation, local remeshing and interface problems. The geometry of boundary edges and facets can be recovered by the introduction of Steiner points. However, for a fully constrained Delaunay triangulation, these Steiner points have to be removed or repositioned towards the interior of the domain to restore the topological integrity of the boundary edges and the facets. It is found that Steiner points on edges could be removed more systematically following a specific sequence in an alternative manner rather than a random selection commonly adopted in practice; whereas for Steiner points on a facet, a weight on the Steiner point adjacency would lead to an optimal order to facilitate their removal. A linear programming technique is also employed to determine the feasible region for the relocation of Steiner points in the interior of the domain. Work examples and industrial applications with details in the boundary recovery are presented to illustrate how the algorithm works on objects with difficult boundary conditions.

Finding correspondences between two sets of visual features of 2D image is a key problem in computer vision tasks. In practice situation, objects often undergo occlusion, background clutter, illumination and 3D viewpoint changes which increase the difficulties of matching, thus a robust matching method is needed to tackle with these problems. In this paper, we propose a robust approach to image matching based on Hessian affine region detector and local Delaunay triangulation and affine invariant geometric constraint. Firstly, Hessian affine keypoints with Scale Invariant Feature Transform(SIFT) descriptors are extracted for model and scene image, then matching the Hessian affine keypoints to get initial matched keypoints based on Euclidean distance of their (SIFT) descriptors. Third, Delaunay triangulation of the initial matched Hessian affine keypoints. Based on unique topological structure of Delaunay triangulation of a set of keypoints, we divide the keypoints into two classes, one class with the same number of neighbor triangles, the other class with different number of neighbor triangles, from the two classes of keypoints, we obtained matched triangles by local Delaunay triangulation. There are may have wrong matched triangles, we adopt local affine invariant geometric constraint to refine the matched triangles. Finally, get the final matched keypoints from the refined matched triangles. By using three pairs of images, the experimental results indicate that the proposed method can get higher correctness of image matching than RANSAC based method.

Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.

In this paper, a new particle matching algorithm for 3D-PIV is proposed based on Delaunay triangulation and projective invariants. In the proposed algorithm, fuzzy similarity is first computed for the triangulation in the matching particle images and rough matching is executed. Then, error matching in the results of rough matching is removed based on projective invariants. Experiment results further demonstrate the effectiveness of the proposed method.

Amongst the flourishing Delaunay Triangulation methods, growth algorithm has been widely accepted because of its reputation of being simple and elegant. However, the parallelization of growth algorithm has not been fully exploited. In this work, a novel Growth algorithm of Delaunay Triangulation is proposed. The point cloud is first divided into two parts by a suitable curve and the separated areas are calculated by incremental algorithm. Triangles which cross with the curve are generated by a growth algorithm associated with uniform grid. At the process of merging, these grew triangles are used to detect incorrect triangles of the incremental algorithm areas. Method about generating triangles on curve is elaborated and a simple way to detect interferential triangles is also explained. With above method, triangulation calculation can be parallelized. Unlike the traditional divide-and-conquer method, no flip operation is needed in the proposed methodology. Thus, three dimensional applications are also made possible. A comparative research between tradition incremental algorithm and the proposed method has been conducted. Results show, the algorithm has a higher performance with less computation time.

By using Delaunay triangulation algorithm, triangulating with split-merge algorithm and the incremental insertion algorithm, improving the judgment that if the new inserted point meets the Delaunay triangulation "empty circle" criterion in synthesis algorithm, meanwhile, with the corresponding improvement of the LOP optimization algorithm, the design of weldment model in the virtual welding system has achieved good result.

Target position is a critical step in the process of constructing Delaunay triangulation. This paper establishes an improved incremental insertion method which realizes fast location based on moving center of gravity along the search direction. It is effective to solve unstable searching path problem usually occurring in some special cases, such as the line from target point to current center of gravity passes through a vertex of a triangle or coincides with a triangle edge. Simulation results show that there exists only location path using this method and the constructing efficiency is increased.

It is so valuable that models merging of Delaunay triangulation are used widely in many applications. This paper researches the algorithm of models merging for Delaunay triangulation. A method for obtaining merged intersection lines and a algorithm for searching fast triangles in the extent of merging intersection lines are proposed, and whole process of models merging are expatiated detailedly. The algorithm is tested in experiments, and the result of experiment shows that this algorithm is very efficient.

We focus on the problem of segmenting scattered point data into multiple regions in a single segmentation pass. To solve this problem, we begin with a set of potential boundary points and use a Delaunay triangulation to complete the boundaries. We then use information from the triangulation and its dual Voronoi complex to determine for each face whether it resembles a boundary or interior face, allowing a user to choose a specific segmentation by keeping only faces where our parameter is above a threshold. The resulting algorithm has time complexity in O(nd), where n is the number of Delaunay simplices.

Hole filling of teeth and gums is an essential stage in orthodontics after segmentation. The patching mesh should keep the morphological features of generic teeth and gums while avoiding collision between two adjacent teeth. This paper presents an efficient hole-filling algorithm to reconstruct the missing part of teeth and gums. Our proposed method involves four necessary steps: boundary construction and projection, hole triangulation in 2D, back projection of vertices to 3D, and mesh fairing. By combining constrained Delaunay triangulation in 2D with back projection of vertices to 3D using mean value coordinates, we achieve high robustness of hole triangulation and a high-quality initial patching mesh. In addition, we propose an automatic method to control the deformation degree to avoid collision. Our experiments demonstrate that the proposed method can achieve satisfactory results, not only in morphology, but also in efficiency. The results are very similar to real teeth and gums and can meet the requirements of orthodontics in medicine.

Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations (DTs). However, the point insertion sequence has a great impact on the amount of work needed for the construction of DTs. It affects the time for both point location and structure update, and hence the overall computational time of the triangulation algorithm. In this paper, a simple deterministic insertion sequence is proposed based on the breadth-first-search on a Kd-tree with some minor modifications for better performance. Using parent nodes as search-hints, the proposed insertion sequence proves to be faster and more stable than the Hilbert curve order and biased randomized insertion order (BRIO), especially for non-uniform point distributions over a wide range of benchmark examples.

International audience; Recently, methods have been proposed to reconstruct a 2-manifold surface from a sparse cloud of points estimated from an image sequence. Once a 3D Delaunay triangulation is computed from the points, the surface is searched by growing a set of tetrahedra whose boundary is maintained 2-manifold. Shelling is a step that adds one tetrahedron at once to the growing set. This paper surveys properties that helps to understand the shelling performances: shelling provides most tetrahedra enclosed by the final surface but it can " get stuck " or block in unexpected cases.

In this paper, we propose a method for solving the problem triangulation of a domain between convex polyhedrons in d- dimensional space using Delaunay triangulation in O ( N 2) time. Novelty of our work is in using a modified Delaunay triangulation algorithm with constraints.

In the light of the simplicity and the linearity of regular grid insertion, a multi-grid insertion scheme is proposed for the Delaunay triangulation of uniform and non-uniform point distributions by recursive application of the regular grid insertion to an arbitrary subset of the original point set. The fundamentals and difficulties of Delaunay triangulation of highly non-uniformly distributed points by the insertion method are discussed. Current strategies and methods of point insertions for non-uniformly distributed points are reviewed. An enhanced kd-tree insertion scheme with specified number of points in a cell and its natural sequence of insertion are presented. The regular grid insertion, the enhanced kd-tree insertion and the multi-grid insertion have been thoroughly tested with benchmark non-uniform distributions of 1-100million points. It is found that the kd-tree insertion is very sensitive to the triangulation of non-uniform point distributions with a large amount of conflicting elongated triangles. Multi-grid insertion is the most stable and efficient for all the uniform and non-uniform point distributions tested.

When Delaunay triangulation is performed in an incremental fashion, different steps are involved in the process. Within those steps “reconstruction” is the most important stage when a new point is randomly inserted. Although there are several techniques to perform this reconstruction, one of the most relevant is a validation technique called “empty circle”, described by Boris Delone. In this paper, we focus on the use of the Conformal Geometric Algebra (CGA) to perform such validation. In addition, the proposal includes a mathematical environment change to show the advantages of using CGA’s geometric entities and use them inside a module for validating the triangulation.

This paper presents a variational method to generate cell complexes with local anisotropy conforming to the Hessian of any given convex function and for any given local mesh density. Our formulation builds upon approximation theory to offer an anisotropic extension of Centroidal Voronoi Tessellations which can be seen as a dual form of Optimal Delaunay Triangulation. We thus refer to the resulting anisotropic polytopal meshes as Optimal Voronoi Tessellations. Our approach sharply contrasts with previous anisotropic versions of Voronoi diagrams as it employs first-type Bregman diagrams, a generalization of power diagrams where sites are augmented with not only a scalar-valued weight but also a vector-valued shift. As such, our OVT meshes contain only convex cells with straight edges, and admit an embedded dual triangulation that is combinatorially-regular. We show the effectiveness of our technique using off-the-shelf computational geometry libraries.

Conventional skeleton extraction method usually limits its applicability due to the close curve or complete boundary constraint. Unfortunately in cluttered image or natural image, the close curve or complete boundary constraint happens all the time. Therefore a skeleton extraction algorithm with an incomplete boundary condition is proposed. The proposed method is based on the Delaunay triangulation of some sampled points from the input image. By using the proposed method, the incomplete boundary condition can be relaxed to some extends.

The Delaunay triangulation is the standard choice for building triangulated irregular networks (TINs) to represent terrain surfaces. However, the Delaunay triangulation is based only on the 2D coordinates of the data points, ignoring their elevation. This can affect the quality of the approximating surface. In fact, it has long been recognized that sometimes it may be beneficial to use other, non-Delaunay, criteria that take elevation into account to build TINs. Data-dependent triangulations were introduced decades ago to address this exact issue. However, data-dependent trianguations are rarely used in practice, mostly because the optimization of data-dependent criteria often results in triangulations with many slivers (i.e., thin and elongated triangles), which can cause several types of problems. More recently, in the field of computational geometry, higher order Delaunay triangulations (HODTs) were introduced, trying to tackle both issues at the same time—data-dependent criteria and good triangle shape—by combining data-dependent criteria with a relaxation of the Delaunay criterion. In this paper, we present the first extensive experimental study on the practical use of HODTs, as a tool to build data-dependent TINs. We present experiments with two USGS 30m digital elevation models that show that the use of HODTs can give significant improvements over the Delaunay triangulation for the criteria previously identified as most important for data-dependent triangulations, often with only a minor increase in running times. The triangulations produced have measure values comparable to those obtained with pure data-dependent approaches, without compromising the shape of the triangles, and can be computed much faster.

The triangulation of convex hull has the characteristics of point-set and polygon triangulation. According to some relative definitions, this paper proposed a triangulation of convex hull based on a monotonic chain. This method is better than Delaunay algorithm and is more efficient than other convex polygon algorithms. It is a good algorithm.

A generic parallel Delaunay triangulation scheme by means of zonal partition of points is presented. For efficient Delaunay triangulation, points are first partitioned into cells, each of which is allocated roughly equal number of points. The cells can be naturally grouped into zones, in which Delaunay triangulation is constructed by simultaneous point insertion cell by cell within each zone. Delaunay triangles/tetrahedra at the boundary between zones can be created in parallel by adding layers of cells at the boundary of each zone to ensure circumcircles(circumspheres) of boundary triangles(tetrahedra) contain no points in their interior. Redundant triangles(tetrahedra) at the boundary between zones can be easily eliminated by individual processors in a completely independent manner by means of the elegant minimum vertex allocation scheme, such that a simplex with k vertices belonging to zones (z1, z2,... zk) is allocated to zone z=min (z1, z2,... zk). A two-dimensional version of the algorithm has been coded in Intel Fortran VS2010. The parallel zonal insertion on a PC can boost the speed of the single-processor insertion by 4.5 times for the insertion of 200 million randomly generated points in 65.7s. The scalability of the parallel zonal insertion algorithm has also been tested on a proper multi-core machine with 12 processors running on OpenMP parallel directives with shared memory. Provided the number of zones is an integral multiple of the number of processors used, almost 100% scalability at 90% efficiency was observed for parallel insertion using 2, 4, 6, 8, 10 and 12 processors, and a 10.6 time speed up was recorded in a parallel insertion of 20 million points in 10x12=120 zones by 12 processors.

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set S, we look for a new point p ∉ S that can be added, such that the shortest path from s to t, in the Delaunay triangulation of S∪{p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

Despite its great success in improving the quality of a tetrahedral mesh, the original optimal Delaunay triangulation (ODT) is designed to move only inner vertices and thus cannot handle input meshes containing ''bad'' triangles on boundaries. In the current work, we present an integrated approach called boundary-optimized Delaunay triangulation (B-ODT) to smooth (improve) a tetrahedral mesh. In our method, both inner and boundary vertices are repositioned by analytically minimizing the L^1 error between a paraboloid function and its piecewise linear interpolation over the neighborhood of each vertex. In addition to the guaranteed volume-preserving property, the proposed algorithm can be readily adapted to preserve sharp features in the original mesh. A number of experiments are included to demonstrate the performance of our method.

A generic parallel Delaunay triangulation scheme by means of zonal partition of points is proposed. For efficient Delaunay triangulation, points are first sorted into cells, each of which is allocated roughly equal number of points. The cells are naturally grouped into zones, in which Delaunay triangulation is constructed by simultaneous point insertion cell by cell within each zone. Tetrahedra at the boundary between zones are created in parallel by adding layers of cells at the boundary of each zone to ensure that circumspheres of boundary tetrahedra contain no points in their interior. Redundant tetrahedra at the boundary between zones can be easily eliminated by individual processors in a completely independent manner by means of the elegant minimum vertex allocation scheme, such that a simplex with k vertices from zones ( z 1 , z 2 , … , z k ) is allocated to zone z = min( z 1 , z 2 , … , z k ). The parallel 3D Delaunay triangulation algorithm has been coded in Intel FORTRAN VS2010. The parallel zonal insertion on a PC can boost the speed of the single-processor insertion by 4.5 times for the insertion of 50 million randomly generated spatial points in 133 s. The scalability of the parallel zonal insertion algorithm has also been tested on a proper multi-core machine with 12 processors running on OpenMP parallel directives with shared memory. Provided the number of zones is an integral multiple of the number of processors used, almost 100% scalability at 90% efficiency was observed for parallel insertion using 2, 4, 6, 8 and 12 processors, and a 10.8 time speed up was recorded in a parallel insertion of 20 million points in 2 × 2 × 3 = 12 zones by 12 processors.

Given a set P of n points in the plane, we show how to compute in O(nlogn) time a spanning subgraph of their Delaunay triangulation that has maximum degree 7 and is a strong plane t-spanner of P with t=(1+2)^[email protected][email protected], where @d is the spanning ratio of the Delaunay triangulation. Furthermore, the maximum degree bound can be reduced slightly to 6 while remaining a strong plane constant spanner at the cost of an increase in the spanning ratio and no longer being a subgraph of the Delaunay triangulation.