| Constructing Delaunay triangulations by merging buckets in quadtree order | |
| Authors: | Jyrki Katajainen and Markku Koppinen |
| Published in: | Fundamenta Informaticae XI,3 (1988), 275-288 |
| Full text: |  PDF (1.87 MB) |
| Copyright: | © Polish Mathematical Society |
| 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 method 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. |
| Related: |  HTML (Thesis) |
| BibLATEX: | @article{KK1988J,
author = {Jyrki Katajainen and Markku Koppinen},
title = {Constructing {D}elaunay triangulations by merging buckets in
quadtree order},
journaltitle = {Fundamenta Informaticae},
volume = {XI},
number = {3},
year = {1988},
pages = {275--288},
}
|