Abstract
This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set ofN points. The first algorithm uses a divide-and-conquer approach. It runs inO(N logN) time, which is asymptotically optimal. The second algorithm is iterative and requiresO(N 2) time in the worst case. However, its average case performance is comparable to that of the first algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Besag, “Spatial interaction and the statistical analysis of lattice systems,”J. Royal Stat. Soc. B 36 (2):192–236 (1974).
D. J. Bogue, “The Structure of the Metropolitan Community,” University of Michigan Contributions of the Institute of Human Adjustment Social Science, University of Michigan, Ann Arbor, Michigan (1949).
B. Delaunay, “Sur la sphère vide,”Bull. Acad. Science USSR VII:Class. Sci. Mat. Nat. 793–800 (1934).
H. Fuchs and Z. M. Kedem, “The Highly Intelligent Tablet as an Efficient Printing Device for Interactive Graphics,” University of Texas (Dallas) (1979). Program in Math. Science (1979).
M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, “Triangulating a simple polygon,”Inform. Proc. Letters 7:175–179 (June 1978).
E. N. Gilbert, “Random subdivision of space into crystals,”Ann. Math. Stat. 33: 958–972 (1962).
P. J. Green and R. Sibson, “Computing Dirichlet tesselations in the plane,”Computer J. 21 (2):168–173 (July 1978).
T.Kiang, “Random fragmentation in two and three dimensions,”Z. Astrophysik 64:433–439 (1966).
C. L. Lawson, “Generation of a Triangular Grid with Applications to Contour Plotting,” Technical Memo. 299, Jet Propulsion Laboratory, Pasadena, California (February 1972).
C. L. Lawson, “Software forC 1 surface interpolation,”in Mathematical Software III, J. Rice, Ed. (Academic Press, New York, 1977).
D. T. Lee, “On Finding κ-Nearest Neighbors in the Plane,” Technical Report Eng. 76-2216, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois (1976).
D. T. Lee, “Proximity and Reachability in the Plane,” Ph.D. Thesis, Coordinated Science Laboratory Report ACT-12, University of Illinois, Urbana, Illinois (1978).
D. T. Lee, “Two-dimensional Voronoi diagrams in theL p-metric,”J. ACM (accepted for publication).
D. T. Lee and C. K. Wong, “Voronoi diagrams inL 1 (L ∞) metrics with two-dimensional storage applications,”SIAM J. Computing (accepted for publication).
B. A. Lewis and J. S. Robinson, “Triangulation of planar regions with applications,”Computer J. 21 (4):324–332 (Nov. 1978).
E. L. Lloyd, “On Triangulation of a Set of Points in the Plane,” Technical Report MIT/LCS/TM-88, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts (May 1977).
P. E. Lloyd and P. Dicken,Location in Space: A Theoretical Approach to Economic Geography (Harper and Row, New York, 1972).
B. Matern, “Spatial variation,”Medd. Statens Skogsforskninginstit. 36 (5):1–144 (1960).
D. H. McLain, “Two dimensional interpolation from random data,”Computer J. 19 (2):178–181 (1976); Errata,Computer J. 19 (4):384 (1976).
R. E. Miles, “Solution to problem 67-15 (Probability distribution of a network of triangles),”SIAM Rev. 11:399–402 (1969).
R. E. Miles, “On the homogeneous planar Poisson point-process,”Math. Biosciences 6:85–127 (1970).
J. Molnar, “Packing of congruent spheres in a strip,”Acta Math. Acad. Sciences Hungaricae Jomus 31 (1–2):173–183 (1978).
J. M. Nelson, “A triangulation algorithm for arbitrary planar domains,”Appl. Math. Modelling 2:151–159 (September 1978).
E. C. Pielou,Mathematical Ecology (Wiley, New York, 1977).
M. J. D. Powell and M. A. Sabin, “Piecewise quadratic approximations on triangles,”ACM Trans. Math. Software 3 (4):316–325 (December 1977).
F. P. Preparata and S. J. Hong, “Convex hulls of finite sets of points in two and three dimensions,”Comm. ACM 20 (2):87–93 (February 1977).
D. Rhynsburger, “Analytic delineation of Thiessen polygons,”Geographical Analysis 5 (2):133–144 (April 1973).
C. A. Rogers,Packing and Covering (Cambridge University Press, 1964).
B. Schachter, A. Rosenfeld, and L. S. Davis, “Random mosaic models for textures,”IEEE Trans. Systems, Man, and Cybernetics 8 (9):694–702 (September 1978).
B. J. Schacter, “Decomposition of polygons into convex sets,”IEEE Trans. Computers C-72 (11):1078–1082 (November 1978).
M. I.Shamos,Computational Geometry (Springer-Verlag, New York, 1977).
M. I. Shamos and D. Hoey, “Closest-point problems,”Proceedings of the 16th Annual Symposium on the Foundations of Computer Science, pp. 151–162 (October 1975).
R. Sibson, “Locally equiangular triangulations,”Computer J. 21 (3):243–245 (August 1978).
B. Stears, “Probability distribution of a network of triangles (Problem 67-15),”SIAM Rev. 11:399 (1969).
P. Switzer, “Reconstructing patterns from sampled data,”Ann. Math. Stat. 38:138–154 (1967).
A. H. Thiessen, “Precipitation averages for large areas,”Monthly Weather Rev. 39:1082–1084 (1911).
G.Voronoi, “Nouvelles applications des parametres continus à la théorie des formes quadratiques. Deuxième Mémoire: Recherches sur les parallelloedres primitifs,”J. Reine Angew. Math. 134: 198–287 (1908).
Author information
Authors and Affiliations
Additional information
This work was supported in part by the National Science Foundation under grant MCS-76-17321 and the Joint Services Electronics Program under contract DAAB-07-72-0259.
Rights and permissions
About this article
Cite this article
Lee, D.T., Schachter, B.J. Two algorithms for constructing a Delaunay triangulation. International Journal of Computer and Information Sciences 9, 219–242 (1980). https://doi.org/10.1007/BF00977785
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00977785