Delaunay triangulation and the convex hull of n points in expected linear time. (English) Zbl 0548.68068

An algorithm is presented which produces a Delaunay triangulation of n points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull of n points in the Euclidean plane.


68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity
52A10 Convex sets in \(2\) dimensions (including convex curves)
68P10 Searching and sorting
05A17 Combinatorial aspects of partitions of integers
51M20 Polyhedra and polytopes; regular figures, division of spaces
Full Text: DOI


[1] A. Aho, J. Hopcroft and J. Ullman,The Design and Analysis of Computer Algorithms, (Addison-Wesley, 1974). · Zbl 0326.68005
[2] S. G. Akl,A constant-time parallel algorithm for computing convex hulls, BIT 22 (1982), 2. · Zbl 0482.68065
[3] K. E. Brassel and D. Reif,A procedure to generate Thiessen polygons, Geograph. Analys. 11, No. 3, July 1979.
[4] B. Delaunay,Sur la sphere vide, Bull. Acad. Sci. USSR(VII), Classe Sci. Mat. Nat., (1934), p. 793–800. · Zbl 0010.41101
[5] W. F. Eddy,A new convex hull algorithm for planar set, ACM Trans. on Math. Softw. 3, (1977), 4. · Zbl 0374.68036
[6] R. J. Fowler,Deltri. A program for inductively computing Delaunay triangulations, Tech. rep. no. 18, Geogr. Data Struct. Project., Dep. of Geogr., Simon Fraser Univ., Durnaby, British Columbia.
[7] R. L. Graham,An efficient algorithm for determining the convex hull of a finite planar set, Inf. Proc. Letters, vol. 1, (1972), p. 132–133. · Zbl 0236.68013
[8] P. J. Green and R. Sibson,Computing Dirichlet tessellation in the plane, The Comp. J. 21, (1978), 168–173. · Zbl 0377.52001
[9] D. T. Lee,Two-dimensional Voronoi diagrams in the Lp-metric, Journ. ACM 27, (1980) 604–618. · Zbl 0445.68053
[10] D. T. Lee and B. J. Schachter,Two algorithms for constructing a Delaunay trinagulation, Int. J. of Comp. and Inf. Sci. 9, (1980), 3. · Zbl 0441.68047
[11] M. J. McCullagh and C. G. Ross,Delaunay triangulation of a random set of data for isarithmic mapping, Cartogr. J., Dec. 1980.
[12] B. D. Ripley,Modelling spatial patterns, J. Roy. Stat. Soc. B39, (1977), p. 172–192.
[13] M. I. Shamos and J. L. Bentley,Optimal algorithms for structuring geographic data, in:An advanced study symposium on topological data structures for geographic information systems, Lab. for Comp. Graphics and Spat. Analys., Harvard Univ., Oct. 1977.
[14] M. I. Shamos and D. Hoey,Closest-point problems, Proc. of the Sixteenth Symp. of Found. of Comp. Sci., IEEE, Oct. 1975.
[15] R. Sibson,The Dirichlet tessalation as an aid in data analysis, Scand. J. Stat. 7, (1980), p. 14–20. · Zbl 0435.62060
[16] R. Sibson,Locally equiangular triangulations, The Comp. J. 21, (1978), 243–245.
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.