Paper Info
Title
Dewall: A Fast Divide And Conquer Delaunay Triangulation Algorithm In E-D
Abstract
The paper deals with Delaunay Triangulations (DT) in E-d space. This classic computational geometry problem is studied from the point of view of the efficiency, extendibility to any dimensionality, and ease of implementation. A new solution to DT is proposed, based on an original interpretation of the well-known Divide and Conquer paradigm. One of the main characteristics of this new algorithm is its generality: it can be simply extended to triangulate point sets in any dimension. The technique adopted is very efficient and presents a subquadratic behaviour in real applications in E-3, although its computational complexity does not improve the theoretical bounds reported in the literature. An evaluation of the performance on a number of datasets is reported, together with a comparison with other DT algorithms. (C) 1998 Published by Elsevier Science Ltd. All rights reserved.
Year
DOI
Venue
1998
10.1016/S0010-4485(97)00082-1
COMPUTER-AIDED DESIGN
Keywords
DocType
Volume
Delaunay triangulation, divide and conquer, uniform grids
Journal
30
Issue
ISSN
Citations 
5
0010-4485
59
PageRank 
References 
Authors
3.23
13
3
Name
Order
Citations
PageRank
paolo cignoni121811.65
Claudio Montani21595135.33
R. Scopigno327421.45