PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Cignoni P., Montani C., Scopigno R. DeWall: a fast divide & conquer Delaunay triangulation algorithm in E. Internal note CNUCE-B4-95-022, 1995.
 
 
Abstract
(English)
The paper deals with Delaunay Triangulations (DT) in Ed space. This classic computational geometry problem is studied from the point of view of the tendency, extendibility to any dimensionality, and ease of implementation new solution for DT is proposed, based on an original interpretation of the wellknown Divide and Conquer (D&C)i paradigm. One of the main characteristics of this new algorithm is its generality: it can be- simply extended to triangulate pointsetsin 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
Subject Delaunay triangulation
Divide Sc conquer
Optimization techniques
Uniform grids


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