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 17 articles , 1 standard article )

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

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