Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Shewchuk, J. R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 305–363 (1997)
Borouchaki, H., George, P. L., Lo, S. H.: Optimal Delaunay point insertion. Int. J. for Num. Methods in Engg. 39, 3407–3437 (1996)
Borouchaki, H., Lo, S. H.: Fast Delaunay triangulation in three dimensions. Computer Methods in Applied Mechanics and Engineering 128, 153–167 (1995)
Joe, B.: Construction of three-dimensional Delaunay triangulations using local transformations. Computer Aided Geometric Design 10, 123–142 (1989)
Edelsbrunner, H., Shah, N. R.: Incremental topological flipping works for regular triangulations. Algorithmica 15, 223–241 (1996)
Amenta, N., Choi, S., Rote, G.: Incremental constructions con BRIO. In: Proc. 19th Annu. ACM Sympos. Comput. Geom. 211–219 (2003)
Liu, Y., Snoeyink, J.: A comparison of five implementations of 3rd Delaunay tesselation. Combinatorial and Computational Geometry 52, 439–458 (2005)
Zhou, S., Jones, C. B.: HCPO: an efficient insertion order for incremental Delaunay triangulation. Inf. Process. Lett. 93, 37–42 (2005)
Boissonnat, J. D., Devillers, O., Samuel, H.: Incremental construction of the Delaunay graph in medium dimension. In: Proc. 25th Annual Symposium on Computational Geometry, 208–216 (2009)
Buchin, K.: Organizing point sets: Space-filling curves, Delaunay tessellations of random point sets, and flow complexes. [Ph.D. Thesis], Free University, Berlin (2007)
Buchin, K.: Constructing Delaunay triangulations along space-filling curves. In: Proc. 2nd Internat. Sympos. Voronoi Diagrams in Science and Engineering, 184–195(2005)
CGAL Editorial Board: CGAL User and Reference Manual. Edition 4.0, 2167–2387 (2012)
Peano, G.: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36, 157–160 (1890) (in German)
Hilbert, D.: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38, 459–460 (1891)
Guibas, L. J., Knuth, D. E., Sharir, M.: Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 381–413 (1992)
de Berg, M., van Kreveld, M., Overmars, M., et al.: Computational Geometry: Algorithms and Applications. 2nd ed. Springer-Verlag, Berlin, Germany (2000)
Devroye, L., Mücke, E., Zhu, B.: A note on point location in Delaunay triangulations of random points. Algorithmica 22, 477–482 (1998)
Devroye, L., Lemaire, C., Moreau, J. M.: Fast Delaunay point location with search structures. In: Eleventh Canadian Conference on Computational Geometry, 15–18 (1999)
Devroye, L., Lemaire, C., Moreau, J. M.: Expected time analysis for Delaunay point location. Computational Geometry 29, 61–89 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
The project was supported by the National Natural Science Foundation of China (10972006 and 11172005) and the National Basic Research Program of China (2010CB832701).
Rights and permissions
About this article
Cite this article
Liu, JF., Yan, JH. & Lo, S.H. A new insertion sequence for incremental Delaunay triangulation. Acta Mech Sin 29, 99–109 (2013). https://doi.org/10.1007/s10409-013-0001-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10409-013-0001-x