Premium
Parallel 3D Delaunay Triangulation
Author(s) -
Cigi P.,
Montani C.,
Perego R.,
Scopigno R.
Publication year - 1993
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.1230129
Subject(s) - delaunay triangulation , bowyer–watson algorithm , computer science , pitteway triangulation , constrained delaunay triangulation , surface triangulation , computer graphics (images) , point set triangulation , triangulation , artificial intelligence , computer vision , algorithm , mathematics , geometry
The paper deals with the parallelization of Delaunay triangulation algorithms, giving more emphasis to pratical issues and implementation than to theoretical complexity. Two parallel implementations are presented. The first one is built on De Wall, an Ed triangulator based on an original interpretation of the divide & conquer paradigm. The second is based on an incremental construction algorithm. The parallelization strategies are presented and evaluated. The target parallel machine is a distributed computing environment, composed of coarse grain processing nodes. Results of first implementations are reported and compared with the performance of the serial versions running on a Unix workstation.