PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Cignoni P., Montani C., Scopigno R. A new Merge-First divide & conquer algorithm for ed delaunay triangulations. internal Report C92/16. Internal note CNUCE-B4-92-016, 1992.
 
 
Abstract
(English)
The paper deals with Delaunay triangulations in Ed 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 Ed of an algorithm originally proposed for E2 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 dataset is reported.
Subject delaunay triangulations


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional