DeWall:: A fast divide and conquer Delaunay triangulation algorithm in Ed

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.