A comparison of sequential Delaunay triangulation algorithms |
| |
Authors: | Peter Su Robert L Scot Drysdale |
| |
Institution: | a Justsystem Pittsburgh Research Center, 4616 Henry Street, Pittsburgh, PA 15213, USA b Department of Computer Science, 6211 Sudikoff Laboratory, Dartmouth College, Hanover, NH 03755-3510, USA |
| |
Abstract: | This paper presents an experimental comparison of a number of different algorithms for computing the Delaunay triangulation. The algorithms examined are: Dwyer's divide and conquer algorithm, Fortune's sweepline algorithm, several versions of the incremental algorithm (including one by Ohya, Iri and Murota, a new bucketing-based algorithm described in this paper, and Devillers's version of a Delaunay-tree based algorithm that appears in LEDA), an algorithm that incrementally adds a correct Delaunay triangle adjacent to a current triangle in a manner similar to gift wrapping algorithms for convex hulls, and Barber's convex hull based algorithm. Most of the algorithms examined are designed for good performance on uniformly distributed sites. However, we also test implementations of these algorithms on a number of non-uniform distributions. The experiments go beyond measuring total running time, which tends to be machine-dependent. We also analyze the major high-level primitives that algorithms use and do an experimental analysis of how often implementations of these algorithms perform each operation. |
| |
Keywords: | Voronoi diagram Delaunay triangulation Experimental analysis of algorithms Practical algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|