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

Maus, Arne

BIT 24, 151-163 (1984).

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.

MSC:

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

Keywords:

Voronoi polygons; Delaunay triangulation; Radix-sort algorithm; linear time algorithm; convex hull; Euclidean plane

References:

[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.