Construction of three-dimensional Delaunay triangulations using local transformations. (English) Zbl 0729.65120

For a set of points in \(R^ 3\) the problem of Delaunay triangulation is to find a set of nonoverlapping tetrahedra that fill the convex hull of the set so that no point is in the circumscribed sphere of any tetrahedron of which it is not a vertex. The author gives the pseudocode description of two programs that solve the problem by local decisions involving five points at a time and proves that the worst case time complexity is \(O(n^ 2)\) and the expected complexity for random points is O(n(log n)\({}^ 2)\).


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
14Q15 Computational aspects of higher-dimensional varieties
32B25 Triangulation and topological properties of semi-analytic andsubanalytic sets, and related questions
Full Text: DOI


[1] Avis, D.; Bhattacharya, B.K., Algorithms for computing d-dimensional Voronoi diagrams and their duals, (), 159-180
[2] Bentley, J.L.; Kung, H.T.; Schkolnick, M.; Thompson, C.D., On the average number of maxima in a set of vectors and applications, J. ACM, 25, 536-543, (1978) · Zbl 0388.68056
[3] Bowyer, A., Computing Dirichlet tessellations, Computer J., 24, 162-166, (1981)
[4] Cavendish, J.C.; Field, D.A.; Frey, W.H., An approach to automatic three-dimensional finite element mesh generation, Int. J. num. meth. eng., 21, 329-347, (1985) · Zbl 0573.65090
[5] Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer Berlin · Zbl 0634.52001
[6] Edelsbrunner, H., An acyclicity theorem for cell complexes in d dimensions, Proc. 5th ACM symp. on computational geometry, 145-151, (1989)
[7] Edelsbrunner, H.; Preparata, F.P.; West, D.B., Tetrahedrizing point sets in three dimensions, J. symbolic computation, (1990), to appear · Zbl 0717.68101
[8] Ferguson, N., Delaunay edge swapping in thre dimensions, Technical report, (1987), Institute for Numerical Computation and Analysis Dublin, Ireland
[9] Joe, B., Delaunay triangular meshes in convex polygons, SIAM J. sci. stat. comput., 7, 514-539, (1986) · Zbl 0637.65121
[10] Joe, B., Three-dimensional triangulations from local transformations, SIAM J. sci. stat. comput., 10, 718-741, (1989) · Zbl 0681.65087
[11] Knuth, D.E., The art of computer programming; vol. 3: searching and sorting, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[12] Lawson, C.L., Software for C1 surface interpolation, (), 161-194
[13] Lawson, C.L., Properties of n-dimensional triangulations, Computer aided geometric design, 3, 231-246, (1986) · Zbl 0624.65018
[14] Petersen, C.S.; Piper, B.R.; Worsey, A.J., Adaptive contouring of a trivariate interpolant, (), 385-395
[15] Preparata, F.P.; Shamos, M.I., Computational geometry, an introduction, (1985), Springer New York · Zbl 0575.68059
[16] Sloan, S.W., A fast algorithm for constructing Delaunay triangulations in the plane, Adv. eng. software, 9, 34-55, (1987) · Zbl 0628.68044
[17] Watson, D.F., Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Computer J., 24, 167-172, (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.