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.gif>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.gif>HTML (Thesis)  
  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},
This page was generated by Jyrki Katajainen <> on 31.12.2011.