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.

References in zbMATH (referenced in 19 articles , 1 standard article )

Showing results 1 to 19 of 19.
Sorted by year (citations)

  1. Yang, Huanhuan; Gunzburger, Max; Ju, Lili: Fast spherical centroidal Voronoi mesh generation: a Lloyd-preconditioned LBFGS method in parallel (2018)
  2. Liebscher, Steffen; Kirschstein, Thomas; Becker, Claudia: RDELA -- a Delaunay-triangulation-based, location and covariance estimator with high breakdown point (2013)
  3. Demaret, Laurent; Iske, Armin; Khachabi, Wahid: Sparse representation of video data by adaptive tetrahedralizations (2012)
  4. Pronzato, Luc; Müller, Werner G.: Design of computer experiments: space filling and beyond (2012)
  5. Batista, Vicente H. F.; Millman, David L.; Pion, Sylvain; Singler, Johannes: Parallel geometric algorithms for multi-core computers (2010)
  6. Schulz, Henrik: Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets (2009)
  7. Apu, Russel Ahmed; Gavrilova, Marina L.: Efficient swarm neighborhood management using the layered Delaunay triangulation (2008)
  8. Fragakis, Yannis; Oñate, Eugenio: Parallel Delaunay triangulation for particle finite element methods (2008)
  9. Ivanov, E. G.: Automatic parallel generation of three-dimensional unstructured grids for computational mechanics (2006)
  10. Ivanov, E. G.; Andrä, H.; Kudryavtsev, A. N.: Domain decomposition approach for automatic parallel generation of tetrahedral grids (2006)
  11. Beyer, Tilo; Schaller, Gernot; Deutsch, Andreas; Meyer-Hermann, Michael: Parallel dynamic and kinetic regular triangulation in three dimensions (2005) ioport
  12. Wu, Y.; Ozdamar, L.; Kumar, A.: TRIOPT: A triangulation-based partitioning algorithm for global optimization (2005)
  13. Kohout, Josef; Kolingerová, Ivana: Parallel Delaunay triangulation in (E^3): make it simple (2003) ioport
  14. Kolingerová, I.: Modified DAG location for Delaunay triangulation (2002)
  15. Krysl, Petr; Ortiz, Michael: Variational Delaunay approach to the generation of tetrahedral finite element meshes (2001)
  16. Lemaire, C.; Moreau, J.-M.: A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case (2000)
  17. Rodríguez, Angel; Espadero, José Miguel; López, Domingo; Pastor, Luis: Delaunay surface reconstruction from scattered points (2000)
  18. Cignoni, P.; Montani, C.; Scopigno, R.: DeWall: a fast divide and conquer Delaunay triangulation algorithm in (E^d). (1998)
  19. Cignoni, P.; Montani, C.; Perego, R.; Scopigno, R.: Parallel 3D Delaunay triangulation. (1993) ioport