A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions

Sariel Har-Peled. and Alper Ungor

We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes O(n log n + m) time, where n is the input size and m is the output size. This is the first time-optimal Delaunay refinement algorithm.

Postscript, PDF.

@string{SOCG_2005 = "Proc. 21st Annu. ACM Sympos. Comput. Geom."}

@inproceedings{hu-todra-05,
  author       = {S. {Har-Peled} and A. {\"U}ng{\"o}r},
  title        = {A Time-Optimal Delaunay Refinement Algorithm in Two
                  Dimensions},
  note         = {\urlSarielPaper{04/opt\_del/}},
  booktitle    = SOCG_2005,
  pages        = {228--236},
  year         = {2005}

Last modified: Sun Jun 26 12:00:05 CDT 2005