A fast divide and conquer Delaunay triangulation algorithm in E^d

Computer-Aided Design, Elsevier, Vol 30, pp.333-341, 1998

MESHING
RESEARCH
CORNER

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 E3, 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.