Two algorithms for constructing a Delaunay triangulation |
| |
Authors: | D. T. Lee B. J. Schachter |
| |
Affiliation: | (1) Northwestern University Dept. of Electrical Engineering and Computer Science, 60201 Evanston, Illinois;(2) General Electric Co., P.O. Box 2500, 32015 Daytona Beach, Florida |
| |
Abstract: | This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set ofN points. The first algorithm uses a divide-and-conquer approach. It runs inO(N logN) time, which is asymptotically optimal. The second algorithm is iterative and requiresO(N2) time in the worst case. However, its average case performance is comparable to that of the first algorithm.This work was supported in part by the National Science Foundation under grant MCS-76-17321 and the Joint Services Electronics Program under contract DAAB-07-72-0259. |
| |
Keywords: | Delaunay triangulation triangulation divide-and-conquer Voronoi tessellation computational geometry analysis of algorithms |
本文献已被 SpringerLink 等数据库收录! |