An evaluation of point-insertion sequences for incremental Delaunay tessellations
- PDF / 2,782,462 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 76 Downloads / 180 Views
An evaluation of point-insertion sequences for incremental Delaunay tessellations Sanderson L. Gonzaga de Oliveira1 · Jéssica Renata Nogueira2
Received: 5 March 2016 / Revised: 29 May 2016 / Accepted: 4 June 2016 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2016
Abstract Currently, incremental algorithms may be seen as the lowest-cost computational methods to generate Delaunay tessellations in several point distributions. In this work, eight point-insertion sequences in incremental algorithms for generating Delaunay tessellations are evaluated. More specifically, four point-insertion sequences in incremental algorithms for generating Delaunay tessellations are proposed: with orders given by the red–black tree with in-order and level-order traversals, spiral ordering, and H-indexing. These four incremental algorithms with such sequences are compared with four incremental algorithms with pointinsertion orders given by the following sequences: the Hilbert and Lebesgue curves, cutlongest-edge kd-tree, and random order. Six 2-D and seven 3-D point distributions are tested, with sets ranging from 25,000 to 8,000,000 points. The results of computational and storage costs of these eight algorithms are analyzed. It follows that the incremental algorithm with a point-insertion sequence in the order given by the cut-longest-edge kd-tree shows the lowest computational and storage costs of the sequences tested. Keywords Mesh generation · Delaunay tessellation · Incremental algorithms · Computer-aided design, engineering and manufacturing · Computational geometry and topology · Insertion sequences · Non-uniform point distributions
1 Introduction Meshes are employed in a number of applications, particularly in finite element discretizations, and are key tools in scientific computing. In this field of study, common meshes are
B
Sanderson L. Gonzaga de Oliveira [email protected] Jéssica Renata Nogueira [email protected]
1
Universidade Federal de Lavras, Lavras, Brazil
2
Instituto Federal de Educação, Ciência e Tecnologia do Sul de Minas Gerais/Campus Passos, Passos, Brazil
123
S. L. G. de Oliveira, J. R. Nogueira
Delaunay tessellations. For a d-dimensional point set, a Delaunay tessellation is described as a mesh in which the d-dimensional ball of each polytope lacks inner points. These meshes are popular mainly because they can be built rapidly and have very appealing geometric properties; for example, the Voronoi diagram, a dual mesh of the Delaunay tessellation, may capture proximity (Gonzaga de Oliveira et al. 2014). Furthermore, Delaunay tessellations are used to represent discrete places of a continuous space in a manner that permits the use of numerical methods to compute characteristics of that space (Edelsbrunner 2001). Delaunay tessellations and Voronoi diagrams have been employed in several applications in science and engineering, such as computer graphics, industrial design, medical applications, the modeling of composite and porous materials, deformable objec
Data Loading...
