DeWall 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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\). Zbl 1035.68122Cignoni, P.; Montani, C.; Scopigno, R. 1998 all top 5 Cited by 52 Authors 2 Ivanov, Eh. G. 1 Andrä, Heiko 1 Apu, Russel Ahmed 1 Batista, Vicente H. F. 1 Becker, Claudia 1 Butt, Ali Raza 1 Cameron, Kirk W. 1 Chang, Tyler H. 1 Cignoni, Paolo 1 Demaret, Laurent 1 Espadero, José Miguel 1 Fragakis, Yannis 1 Funke, Daniel 1 Gavrilova, Marina L. 1 Gunzburger, Max D. 1 Hong, Yili 1 Iske, Armin 1 Ju, Lili 1 Khachabi, Wahid 1 Kirschstein, Thomas 1 Kolingerová, Ivana 1 Krysl, Petr 1 Kudryavtsev, Alexey N. 1 Lemaire, Christophe 1 Liebscher, Steffen 1 Liu, Yehong 1 López, Domingo 1 Lux, Thomas C. H. 1 Masood, Talha Bin 1 Millman, David L. 1 Montani, Claudio 1 Moreau, Jean-Michel 1 Müller, Werner G. 1 Natarajan, Vijay 1 Oñate Ibáñez de Navarra, Eugenio 1 Ortiz, Michael 1 Ozdamar, Linet 1 Pastor, Luis 1 Pion, Sylvain 1 Pronzato, Luc 1 Ray, Tathagata 1 Rodríguez, Angel F. Zazo 1 Sanders, Peter 1 Schulz, Henrik 1 Scopigno, Roberto 1 Singler, Johannes 1 Strang, Alexander 1 Watson, Layne Terry 1 Winkler, Vincent 1 Wu, Yong 1 Yang, Huanhuan 1 Yin, Guosheng all top 5 Cited in 13 Serials 3 Computational Geometry 2 Statistics and Computing 1 Discrete Applied Mathematics 1 Journal of Computational Physics 1 ACM Transactions on Mathematical Software 1 International Journal for Numerical Methods in Engineering 1 Journal of Computational and Applied Mathematics 1 SIAM Journal on Discrete Mathematics 1 CAD. Computer-Aided Design 1 Computational Statistics and Data Analysis 1 Communications in Numerical Methods in Engineering 1 Vychislitel’nye Tekhnologii 1 Computational Methods in Applied Mathematics all top 5 Cited in 10 Fields 10 Computer science (68-XX) 9 Numerical analysis (65-XX) 4 Statistics (62-XX) 2 Mechanics of deformable solids (74-XX) 2 Operations research, mathematical programming (90-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Convex and discrete geometry (52-XX) 1 Fluid mechanics (76-XX) 1 Biology and other natural sciences (92-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year