A merge-first divide & conquer algorithm for ed delaunay triangulations

The paper deals with Delaunay triangulations in E?d space, a classic problem in computational geometry, from the point of view of the efficiency and the easy parallelization of the algorithms. The application field is the processing and visualization of large scattered datasets; in this field, the real time visualization of time-varying phenomena is a typical requirement. An extension in E?d of an algorithm originally proposed for E?2 Delaunay triangulations and two simple and effective speedup techniques is first proposed and a new algorithm based on a original interpretation of the well-known Divide and Conquer paradigm is then presented. Although the computational complexity of the algorithm does not improve the theoretical results reported in the literature, the technique is very efficient and present a quasi linear behaviour in real applications. Thanks to the use of a D&C technique, the algorithm can be easily parallelized on low grain parallel architectures (such as shared memory MIMD machines or networks of workstations). An evaluation of the performance on medium resolution datasets is reported.