swMATH ID: 1745
Software Authors: Cignoni, P.; Montani, C.; Scopigno, R.
Description: DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\). 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.
Homepage: http://code.google.com/p/dewall-omp/
Keywords: uniform grids
Related Software: CGAL; Triangle; 2D triangulations; Qhull; DELAUNAYSPARSE; QNSTOP; Algorithm 587; LAPACK; Adam; Voronoi; XGBoost; FSInteract; Scikit; SciPy; UCI-ml; CHEXVIS; CAMPARY; 3D Alpha Shapes; Thrust; CUDA
Cited in: 21 Publications

Citations by Year