Constructing Delaunay Triangulations by Merging Buckets in Quad Tree Order

Article type: Research Article

Authors: Katajainen, Jyrki^{; *} | Koppinen, Markku

Affiliations: Department of Mathematical Sciences, University of Turku, SF-20500 Turku, Finland

Note: [*] Present address: Department of Computer and Information Science, Linköping University, S-581 83 Linköping, SWEDEN. This author’s research was supported by the Academy of Finland.

Abstract: Recently Rex Dwyer [D87] presented an algorithm which constructs a Delaunay triangulation for a planar set of N sites in O(N log log N) expected time and O(N log N) worst-case time. We show that a slight modification of his algorithm preserves the worst-case running time, but has only O(N) average running time. The methcxl is a hybrid which combines the cell technique with the divide-and-conquer algorithm of Guibas & Stolfi [GS85]. First a square grid of size about N by N is placed on the set of sites. The grid forms about N cells (buckets), each of which is implemented as a list of the sites which fall into the corresponding square of the grid. A Delaunay triangulation of the generally rather few sites within each cell is constructed with the Guibas & Stolfi algorithm. Then the triangulations are merged, four by four, in a quadtree-like order.

Keywords: Voronoi diagrams, Delaunay triangulations, bucket methods, quadtrees

DOI: 10.3233/FI-1988-11305

Journal: Fundamenta Informaticae, vol. 11, no. 3, pp. 275-288, 1988