Search

Delaunay-based shape reconstruction algorithms are widely used in approximating the shape from planar points. However, these algorithms cannot ensure the optimality of varied reconstructed cavity boundaries and hole boundaries. This inadequate reconstruction can be primarily attributed to the lack of efficient mathematic formulation for the two structures (hole and cavity). In this paper, we develop an efficient algorithm for generating cavities and holes from planar points. The algorithm yields the final boundary based on an iterative removal of the Delaunay triangulation. Our algorithm is mainly divided into two steps, namely, rough and refined shape reconstructions. The rough shape reconstruction performed by the algorithm is controlled by a relative parameter. Based on the rough result, the refined shape reconstruction mainly aims to detect holes and pure cavities. Cavity and hole are conceptualized as a structure with a low-density region surrounded by the high-density region. With this structure, cavity and hole are characterized by a mathematic formulation called as compactness of point formed by the length variation of the edges incident to point in Delaunay triangulation. The boundaries of cavity and hole are then found by locating a shape gradient change in compactness of point set. The experimental comparison with other shape reconstruction approaches shows that the proposed algorithm is able to accurately yield the boundaries of cavity and hole with varying point set densities and distributions.

A general and direct computational scheme to locate the surface separating arbitrarily shaped domains made up of molecules (or any other particles) has been developed and is described and illustrated for several, both artificial and physical examples. The proposed scheme consists of two modules: (i) triangulation and (ii) assignment of simplices to domains. Three different triangulation methods are employed, viz., the Delaunay triangulation, regular triangulation, and quasi-triangulation. In the triangulated system, the assignment step is carried out in two different ways, one based on the characteristic metric of a particular triangulation procedure and the other on the concept of a touching sphere. Some of the combinations of the triangulation and assignment steps lead to methods already used by others to find interfacial or surface molecules, namely the alpha-shape-based method of Usabiaga nad Duque [Phys. Rev. E 79 (2009) 046709] and GITIM of Sega et al. [J. Chem. Phys. 138 (2013) 044110]. The resulting surface is defined not only as a discrete set of particles, but it is build up of facets of the triangulation forming a broken line in two dimensions or a polyhedral surface in three dimensions. Individual molecular layers are identified in a very straightforward manner, starting with the interfacial layer itself and proceeding into the interior of the phase. The proposed scheme is illustrated first by identifying border molecules of pre-sampled domains of several shapes in a plane and then applied to five physically meaningful examples: thin films, near critical water, liquid water slab in an electric field, liquid water at a solid wall, and water at condition of electric-field-induced jetting. Performance of the considered methods is critically assessed. Treatment of domains forming percolating clusters through periodic boundary conditions is also described along with the determination of their periodicity and dimensionality.

In this paper a novel approach to extract 2D skeleton information (skeletonization) from natural image is proposed. The work presented here is the extension of our previous paper presented at the International Sympsosium on Multimedia 2016. In the past work, a threshold based method is utilized. Here the algorithm is further improved by using a better edge points detection and skeleton extraction. Furthermore the proposed method is compared with the Skeleton Strength Map (SSM) and shows better result visually and numerically (F-measure comparison).

This paper presents a fine grain parallel version of the 3D Delaunay Kernel procedure using the OpenMP (Open Multi-Processing) API. A set S={p1,,pn} of n points is taken as input. S is initially sorted along a space-filling curve so that two points that are close in the insertion order are also close geometrically. The sorted set of points is then divided into M subsets Si, 1iM of equal size n/M. The multithreaded version of the Delaunay kernel inserts M points at a time in the triangulation. OpenMP barriers provide the required synchronization that is needed after each multiple insertion in order to avoid data races. This simple approach exhibits two standard problems of parallel computing: load imbalance and parallel overheads. Those two issues are addressed using a two-level version of the multithreaded Delaunay kernel. Tests show that triangulations of about a billion tetrahedra can be generated on a 32 core machine (Intel Xeon E5-4610 v2 @ 2.30GHz with 128GB of memory) in less that 3 minutes of wall clock time, with a speedup of 18 compared to the single-threaded implementation. A fine grain parallel Delaunay kernel algorithm is proposed.The method that is proposed allows to generate meshes with more than a billion tetrahedra in about two minutes.The implementation uses simple OpenMP constructs.

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.

Multiple dilation rapidly deforms object structure using mathematical morphology.Preserving object structure is of paramount importance in pattern recognition.A new geometric-based mechanism for binary image dilation is proposed.Our method exploits Delaunay triangulation; a versatile geometric structure.Our method shows high performance when applied to handwritten digit classification. Mathematical morphology has been of a great significance to several scientific fields. Dilation, as one of the fundamental operations, has been very much reliant on the common methods based on the set theory and on using specific shaped structuring elements to morph binary blobs. We hypothesised that by performing morphological dilation while exploiting geometry relationship between dot patterns, one can gain some advantages. The Delaunay triangulation was our choice to examine the feasibility of such hypothesis due to its favourable geometric properties. We compared our proposed algorithm to existing methods and it becomes apparent that Delaunay based dilation has the potential to emerge as a powerful tool in preserving objects structure and elucidating the influence of noise. Additionally, defining a structuring element is no longer needed in the proposed method and the dilation is adaptive to the topology of the dot patterns. We assessed the property of object structure preservation by using common measurement metrics. We also demonstrated such property through handwritten digit classification using HOG descriptors extracted from dilated images of different approaches and trained using Support Vector Machines. The confusion matrix shows that our algorithm has the best accuracy estimate in 80% of the cases. In both experiments, our approach shows a consistent improved performance over other methods which advocates for the suitability of the proposed method. Display Omitted

We develop a dimension-independent, Delaunay-based anisotropic mesh generation algorithm suitable for integration with adaptive numerical solvers. As such, the mesh produced by our algorithm conforms to an anisotropic metric prescribed by the solver as well as the domain geometry, given as a piecewise smooth complex. Motivated by the work of Lévy and Dassi [10-12,20], we use a discrete manifold embedding algorithm to transform the anisotropic problem to a uniform one. This work differs from previous approaches in several ways. First, the embedding algorithm is driven by a Riemannian metric field instead of the Gauss map, lending itself to general anisotropic mesh generation problems. Second we describe our method for computing restricted Voronoi diagrams in a dimension-independent manner which is used to compute constrained centroidal Voronoi tessellations. In particular, we compute restricted Voronoi simplices using exact arithmetic and use data structures based on convex polytope theory. Finally, since adaptive solvers require geometry-conforming meshes, we offer a Steiner vertex insertion algorithm for ensuring the extracted dual Delaunay triangulation is homeomorphic to the input geometries. The two major contributions of this paper are: a method for isometrically embedding arbitrary mesh-metric pairs in higher dimensional Euclidean spaces and a dimension-independent vertex insertion algorithm for producing geometry-conforming Delaunay meshes. The former is demonstrated on a two-dimensional anisotropic problem whereas the latter is demonstrated on both 3d and 4d problems. Keywords: Anisotropic mesh generation; metric; Nash embedding theorem; isometric; geometry-conforming; restricted Voronoi diagram; constrained centroidal Voronoi tessellation; Steiner vertices; dimension-independent

Delaunay triangulation is a geometric problem that is relatively difficult to parallelize. Parallel algorithms are usually characterized by considerable interprocessor communication or important serialized parts. In this paper, we propose a method that achieves high speed-ups, but needs information regarding locally maximum element circumspheres prior to the beginning of the algorithm. Such information is directly available in iterative methods, like the particle finite element methods. The developed parallel Delaunay triangulation method, has minimum communication requirements, is quite simple and achieves high parallel efficiency. Copyright © 2007 John Wiley & Sons, Ltd.

Voronoi diagrams are useful for spatial reasoning, and the robust and efficient construction of the ordinary Voronoi diagram of points is well known. However, its counterpart for circular disks in R 2 and spherical balls in R 3 remains a challenge. In this article, we propose a topology-oriented incremental algorithm which robustly and efficiently computes a Voronoi diagram by incrementing a new disk generator to an existing one. The key idea is to enforce the convexity of the Voronoi cell corresponding to the incrementing disk so that a simple variation of the algorithm for points proposed by Sugihara in 1992 can be applied. A benchmark using both random and degenerate disks shows that the proposed algorithm is superior to CGAL in both computational efficiency and algorithmic robustness.

In this paper, we present a generalized prismatic hybrid meshing method for viscous flow simulations. One major difficulty in implementing a robust prismatic hybrid meshing tool is to handle boundary layer mesh collisions and normally an extra data structure (e.g. quadtree in 2D and octree in 3D) is required. The proposed method overcomes this difficulty via an heuristic approach and it only relies on Constrained Delaunay Triangulation/Tetrahedralization(CDT). No extra data structures are required. Geometrical reasoning is used to approximate the maximum marching distance of each point by walking through the CDT. This is combined with post-processing of marching vectors and distance and prohibition of multilevel differences to form an automatic and robust mechanism to remove boundary layer mesh collisions. Benefiting from the matureness of CDT techniques, the proposed method is robust, efficient and simple to implement. Its capability is demonstrated by generating quality prismatic hybrid meshes for industrial models with complex geometries. The proposed method is believed to be able considerably reduce the effort to implement a robust hybrid prismatic mesh generator for viscous flow simulations.

Given the enormous scale and diverse distribution of 2D point cloud data, an adaptive Hilbert curve insertion algorithm which has quasi-linear time complexity is proposed to improve the efficiency of Delaunay triangulation. First of all, a large number of conflicting elongated triangles, which have been created and deleted many times, can be reduced by adopting Hilbert curve traversing multi-grids. In addition, searching steps for point location can be reduced by adjusting Hilbert curve's opening direction in adjacent grids to avoid the "jumping" phenomenon. Lastly, the number of conflicting elongated triangles can be further decreased by adding control points during traversing grids. The experimental results show that the efficiency of Delaunay triangulation by the adaptive Hilbert curve insertion algorithm can be improved significantly for both uniformly and non-uniformly distributed point cloud data, compared with CGAL, regular grid insertion and multi-grid insertion algorithms. Graphical abstractDisplay Omitted HighlightsThe proposed algorithm optimizes the order of inserted points.The order is determined by adaptive Hilbert curve and control points.Conflicting elongated triangles and searching steps are reduced by optimized order.The efficiency of the proposed method is proved to be enhanced by detail experiment.The proposed algorithm is suitable for randomly distributed points.

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.

Finding correspondences between pair of images of the same scene is a key problem in computer vision. When matching images undergo viewpoint change, partial occlusion, clutters and illumination change, there will be a lot of mismatches due to the limited repeatability and discriminative power of features. In this paper, we propose a robust matching algorithm that can remove false matches and propagate the correct ones to obtain more matches, thus improve the matching accuracy. First, extracts SURF (Speeded Up Robust Features) descriptors from the input two images, which can be used to build the proximity matrix. Then perform SVD (Singular Value Decomposition) on the proximity matrix to obtain the initial matches. Third, refine the initial matches by the unique property of Delaunay triangulation that can produce the maximum cliques of the two Delaunay graph. Finally, recover the lost matches with the constraint of dual graph of Voronoi. Experimental results on Oxford datasets indicate that our algorithm can improve the match performance compared to the RANSAC-based method.

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.

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.

A novel parallel simulation algorithm on the GPU, implemented in CUDA and C++, is presented for the simulation of Brownian particles that display excluded volume repulsion and interact with long and short range forces. When an explicit Euler-Maruyama integration step is performed to take into account the pairwise forces and Brownian motion, particle overlaps can appear. The excluded volume property brings up the need for correcting these overlaps as they happen, since predicting them is not feasible due to the random displacement of Brownian particles. The proposed solution handles, at each time step, a Delaunay triangulation of the particle positions because it allows us to efficiently solve overlaps between particles by checking just their neighborhood. The algorithm starts by generating a Delaunay triangulation of the particle initial positions on CPU, but after that the triangulation is always kept on GPU memory. We used a parallel edge-flip implementation to keep the triangulation updated during each time step, checking previously that the triangulation was not rendered invalid due to the particle displacements. The algorithm is validated with two models of active colloidal particles. Upon testing the parallel implementation of a long range forces simulation, the results show a performance improvement of up to two orders of magnitude when compared to the previously existing sequential solution., Due to the limitation "The abstract field cannot be longer than 1,920 characters", the abstract appearing here is slightly shorter than the one in the PDF file

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ?(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ?(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense.

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.

A novel mesh deformation technique is developed based on the Delaunay graph mapping (DGM) method and the radial basis function (RBF) method. The algorithm combines the advantages of the efficiency of DGM mesh deformation and the better control of the near surface mesh quality from the RBF method. The Delaunay graph is used to divide the mesh domain into a number of sub-domains. On each of the sub-domains, the radial basis function is applied to build a much smaller sized translation matrix between the original mesh and the deformed mesh, resulting in a similar efficiency for the mesh deformation as compared to the fast Delaunay graph mapping method. Furthermore, by separating the translation and rotation motion, the mesh quality near the wall can be substantially improved for extremely large rotational deformation. The paper will show how the near-wall mesh quality is controlled and improved by the new method while the computational time is maintained to be comparable to the original Delaunay graph mapping method.

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.

Aiming at complex configuration and large deformation, an efficient hybrid method for dynamic mesh generation is presented in this paper, which is based on Radial Basis Functions (RBFs) and Delaunay graph mapping. Based on the computational mesh, a set of very coarse grid named as background grid is generated firstly, and then the computational mesh can be located at the background grid by Delaunay graph mapping technique. After that, the RBFs method is applied to deform the background grid by choosing partial mesh points on the boundary as the control points. Finally, Delaunay graph mapping method is used to relocate the computational mesh by employing area or volume weight coefficients. By applying different dynamic mesh methods to a moving NACA0012 airfoil, it can be found that the RBFs-Delaunay graph mapping hybrid method is as accurate as RBFs and is as efficient as Delaunay graph mapping technique. Numerical results show that the dynamic meshes for all test cases including one two-dimensional (2D) and two three-dimensional (3D) problems with different complexities, can be generated in an accurate and efficient manner by using the present hybrid method.

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.

A new hybrid h-adaptive algorithm is design to optimize unstructured polygonal meshes in 2D based on Voronoi tessellations and its topological dual, Delaunay triangulations. The algorithm consists of several unique features: first, dynamic change of mesh topology (reconnection of nodes) is realized through refinement and coarsening iterations with specific feature (i.e. Voronoi diagram); second, two moving mesh strategies are included, one is the weighted global smoothing for mesh regulation which is based on centroidal Voronoi tessellations (CVTs), the other is a local smoothing for the purpose of speed-up of the adaptive iterations; third, a new marking strategy with double threshold values guarantee the convergence of adaptive iterations. The advantage of the hybrid algorithm is that the goal mesh resolution can converge to an arbitrarily small number; it asymptotically converges to a straight line in 2D (i.e., the volume equi-distribution error approaches zero). The h-adaptation is referred to as asynchronous process, if the processes of coarsening and refinement are connected through several global mesh regulation steps. Otherwise the hybrid adaptive process is synchronous. This will provide options to meet special requirement such as smooth transition of physical fields. The numerical results show that the numerical errors are indeed well distributed in an averaged sense in the domain, where the mesh sizes are optimal, and nodes of the mesh smoothly follow the underlying geometry or physics. The new hybrid algorithm demonstrates its potential for effectiveness, efficiency and robustness to handle generation and optimization of polygonal meshes for extreme scenarios with a wide spectrum of length scales.

The regular grid discretization is prevalent in the inverse modeling for gravity and magnetic data. However, this subdivision strategy performs lower precision to represent the rugged observation surface. To deal with this problem, we evaluate a non-structured discretization method in which the subsurface with rolling terrain is divided into numbers of Delaunay triangular cells and each mesh has the uniform physical property distributions. The gravity and magnetic anomalies of a complex-shaped anomalous body are represented as the summaries of the single anomaly produced by each triangle field source. When inverting for the potential field data, we specify a minimization objective function composed of data constraints and then use the preconditioned conjugate gradient algorithm to iteratively solve the matrix minimization equations, where the preconditioner is determined by the distances between triangular cells and surface observers. We test our method using synthetic data; all tests return favorable results. In the case studies involving the gravity and magnetic anomalies of the Mengku and Pobei deposits in Xinjiang, northwest China, the inferred magnetite orebodies and ultrabasic rocks distributions are verified by the additional drilling and geological information. The discretization of constrained Delaunay triangulation provides an useful approach of computing and inverting the potential field data on the situations of undulate topography and complicated objects. Use the constrained Delaunay triangulation to divide the subsurface.Implement the preconditioned conjugate gradient inverting for potential fields.Use the synthetic and field data to test the method and return favorable results.Be applicable for the scenarios with undulate topography and complicated objects.

The edges of the Voronoi diagram for a finite set P of points in a compact Riemannian surface are a subset of the cut locus of P. From this point of view we study when the Voronoi cells are homeomorphic to disks, using the mini-type distance function for P and its critical points. We will see some relations between the topological structure and the Voronoi diagram.

This paper presents a fine grain parallel version of the 3D Delaunay Kernel procedure using the OpenMP (Open Multi-Processing) API. A set S = {p1,. . ., pn} of n points is taken as input. S is initially sorted along a space-filling curve so that two points that are close in the insertion order are also close geometrically. The sorted set of point is then divided into M subsets Si, 1 ≤ i ≤ M of equal size n/M. The multithreaded version of the Delaunay kernel inserts M points at a time in the triangulation. OpenMP barriers provide the required synchronization that is needed after each multiple insertion in order to avoid data races. This simple approach exhibits two standard problems of parallel computing: load imbalance and parallel overheads. Those two issues are addressed using a two-level version of the multithreaded Delaunay kernel. Tests show that triangulations of about a billion tetrahedra can be generated on a 32 core machine (Intel Xeon E5-4610 v2 @ 2.30GHz with with 128 GB of memory) in less that 3minutes of wall clock time, with a speedup of 18 compared to the single-threaded implementation.

A triangulation of points in E 2 , or a tetrahedronization of points in E 3 , is used in many applications. It is not necessary to fulfill the Delaunay criteria in all cases. For large data (more then 5 · 10 7 points),parallel methods are used for the purpose of decreasingrun–time. A new approach for fast, effective and highly parallel CPU and GPU triangulation, or tetrahedronization, of large data sets in E 2 or E 3 suitable for in–core and out–core memory processing, is proposed. Experimental results proved that the resulting triangulation/tetrahedralization is close to the Delaunay triangulation/tetrahedralization. It also demonstrates the applicability of the methodproposed in applications.

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.

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.

Voronoi diagram on the earth surface is a powerful tool to study spatial proximity at continental or global scale. However, its computation remains challenging because geospatial features have complex shapes. This paper presents a raster-based algorithm to generate Voronoi diagrams on earth's surface. The algorithm approximates the exact point-to-point geographical distances using the cell-to-cell geographical distances calculated by a geographical distance transform. The result is a distance image on which Voronoi diagram is delineated. Compared to existing methods, the proposed algorithm calculates geographical distances based on an earth ellipsoid and allows Voronoi generators to take complex shapes. Most importantly, its approximation error is bounded thus enabling users to control the accuracy of the Voronoi diagram through grid resolution. We developed a raster-based method to generate Voronoi diagrams on the earth.The method is based on geographical distance transform.Voronoi generators are allowed to have any arbitrary shape.The accuracy of the Voronoi diagram can be controllable through grid resolution.

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.

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.

International audience; We present a method for reconstructing a 3D surface triangulation from an input point set. The main component of the method is an algorithm that computes the restricted Voronoi diagram. In our specific case, it corresponds to the intersection between the 3D Voronoi diagram of the input points and a set of disks centered at the points and orthogonal to the estimated normal directions. The method does not require coherent normal orientations (just directions). Our algorithm is based on a property of the restricted Voronoi cells that leads to an embarrassingly parallel implementation. We experimented our algorithm with scanned point sets with up to 100 million vertices that were processed within few minutes on a standard computer. The complete implementation is provided.

Computational geometry is a mathematical knowlege in the field related to the design and analysis of algorithm to solve geometry problems. Its can be applicated in the fields of mapping, robotics, geometry and so forth. A method can be used is Voronoi diagram. Voronoi diagram is a method of deviding the area to a smaller area based on the principle of the nearest neighboring. This method only used in 1-order voronoi diagram. In voronoi diagram there is a new variation named Highest Order Voronoi Diagram (HSVD). HSVD can be used for all orders voronoi diagram. However, these methods have disadvantage that accessing fragment use linear search. Consequently make data fragment searches to find the region to be slow and takes a long time. Therefore, in this paper will present a index structure that incoperates Highest Order Voronoi Diagrams into Quadtree. Quadtree index used is capable of cutting more than half of the original data. This algorithm makes the search regions faster than before.

Computational geometry is concerned with the design and analysis of algorithms for geometrical problems. In addition, other more practically oriented, areas of computer science-such as computer graphics, computer-aided design, robotics, pattern recognition, and operation research-give rise to problems that inherently are geometrical. A method that is commonly used is Voronoi diagram. Voronoi diagram is a diagram that divides plane based on nearest neighbour approach. This method does not require checking objects one by one. In Voronoi diagram there is a new variation named Highest Order Voronoi Diagram. Highest order voronoi diagram can be used directly to identify the region for various type of spatial queries and can be used for all order Voronoi Diagram. From work related there is a method named FLIP. Deficiency from work related is data structure for construction are too high which makes construction of Highest Order Voronoi Diagram is heavy. Therefore, in this paper will present Left with Least-Angle Movement (LAM) method for construction Highest Order Voronoi Diagram that change data structure to scale up data that can be processed.

We propose the first working GPU algorithm for the 2D Delaunay refinement problem. Our algorithm adds Steiner points to an input planar straight line graph (PSLG) to generate a constrained Delaunay mesh with triangles having no angle smaller than an input θ. It is shown to run from a few times to an order of magnitude faster than the well-known Triangle software, which is the fastest CPU Delaunay mesh generator. Our implementation handles degeneracy and is numerically robust. It is proven to terminate with finite output size for an input PSLG with no angle smaller than 60° and θ ≥ 20.7°. In addition, we notice meshes generated by our algorithm are of similar sizes to that by Triangle, which has incorporated good consideration in keeping output small in size.

The stereo vision problem gives rise to two sub-problems: the correspondence and the stereo calibration. Once the sub-problems have been solved, depth is estimated by triangulation. Depth estimation, using stereo images, is based on disparity – the relative displacement between corresponding points – and the camera geometry. Small errors in disparity may produce large errors in depth estimates due to the ill-posedness nature of the stereo vision problem. Moreover, if the camera geometry is unknown, it is estimated using corresponding points. A solution of stereo vision problem may be improved by identifying corresponding points which are inaccurately estimated. In this paper, the classification of a set of estimated corresponding points uses Delaunay triangulation by restricting it to a given subset of estimated corresponding points. Delaunay edges among estimated corresponding points are used to build undirected graphs. Classification criteria based on adjacencies are defined in order to decide whether or not a corresponding point is correctly estimated. Experimental evaluation, using ground truth image sets for quantitative analysis, shown values of specificity around 70% while sensitivity up to 96%.

In one procedure for finding the maximal prime decomposition of a Bayesian network or undirected graphical model, the first step is to create a minimal triangulation of the network, and a common and straightforward way to do this is to create a triangulation that is not necessarily minimal and then thin this triangulation by removing excess edges. We show that the algorithm for thinning proposed in several previous publications is incorrect. A different version of this algorithm is available in the R package gRbase, but its correctness has not previously been proved. We prove that this version is correct and provide a simpler version, also with a proof. We compare the speed of the two corrected algorithms in three ways and find that asymptotically their speeds are the same, neither algorithm is consistently faster than the other, and in a computer experiment the algorithm used by gRbase is faster when the original graph is large, dense, and undirected, but usually slightly slower when it is directed.

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.

Aiming at the folds caused by the sparse data in the process of DTM (Digital Terrain Model), this article proposed a method of interpolating spatial control points based on Delaunay triangulation and Kriging interpolation algorithm. The terrain data of an area with complex terrain in Xianyang was used to construct terrain model according to the proposed algorithm. Experimental results show that the method can finish the interpolation of the terrain denser data quickly and accurately, and it provides an efficient technological tool for building a true three-dimensional terrain model.

Fractured reservoirs are complex domains where discrete fractures are internal constraining boundaries. The discrete fractures are discretized into intersected edges during a grid-generation process, and Delaunay triangulations are often used to represent complex structures. However, a Delaunay triangulation of a fractured medium generally does not conform to the fracture; recovering the fracture elements may violate the Delaunay empty-circle (2D) criterion and may lead to a low-quality triangulation. Refining the triangulation is not a practical solution in complex fractured media. A new approach combines both Gabriel and Delaunay triangulations. A modified Gabriel condition of edge-empty-circle is introduced and locally employed to quantify the quality of the fracture edges in 2D. The fracture edges violating the modified Gabriel criterion are released in the first stage. After that, a Delaunay triangulation is generated considering the rest of the fracture constraints. The released fracture edges are then approximated by the edges of the Delaunay triangles. The final representation of fractures might be slightly different, but a very accurate approximation is always maintained. The method generates fine and coarse grids and offers an accurate and good-quality grid. Numerical examples are presented to assess the performance and efficiency of the proposed method. Finally, the method can be employed in the pre- and postprocessing stages to various possible meshing algorithms.

We describe a new algorithm for computing the Voronoi diagram of a set of $$n$$n points in constant-dimensional Euclidean space. The running time of our algorithm is $$O(f \log n \log \varDelta )$$O(flognlogΔ) where $$f$$f is the output complexity of the Voronoi diagram and $$\varDelta $$Δ is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.

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.

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.