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

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

1 2 next

  1. Chang, Tyler H.; Watson, Layne T.; Lux, Thomas C. H.; Butt, Ali R.; Cameron, Kirk W.; Hong, Yili: Algorithm 1012. DELAUNAYSPARSE: interpolation via a sparse subset of the Delaunay triangulation in medium to high dimensions (2020)
  2. Liu, Yehong; Yin, Guosheng: The Delaunay triangulation learner and its ensembles (2020)
  3. Masood, Talha Bin; Ray, Tathagata; Natarajan, Vijay: Parallel computation of alpha complexes for biomolecules (2020)
  4. Strang, Alexander: Solutions to the minimum variance problem using Delaunay triangulation (2020)
  5. Funke, Daniel; Sanders, Peter; Winkler, Vincent: Load-balancing for parallel Delaunay triangulations (2019)
  6. Yang, Huanhuan; Gunzburger, Max; Ju, Lili: Fast spherical centroidal Voronoi mesh generation: a Lloyd-preconditioned LBFGS method in parallel (2018)
  7. Liebscher, Steffen; Kirschstein, Thomas; Becker, Claudia: RDELA -- a Delaunay-triangulation-based, location and covariance estimator with high breakdown point (2013)
  8. Demaret, Laurent; Iske, Armin; Khachabi, Wahid: Sparse representation of video data by adaptive tetrahedralizations (2012)
  9. Pronzato, Luc; Müller, Werner G.: Design of computer experiments: space filling and beyond (2012)
  10. Batista, Vicente H. F.; Millman, David L.; Pion, Sylvain; Singler, Johannes: Parallel geometric algorithms for multi-core computers (2010)
  11. Schulz, Henrik: Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets (2009)
  12. Apu, Russel Ahmed; Gavrilova, Marina L.: Efficient swarm neighborhood management using the layered Delaunay triangulation (2008)
  13. Fragakis, Yannis; Oñate, Eugenio: Parallel Delaunay triangulation for particle finite element methods (2008)
  14. Ivanov, E. G.: Automatic parallel generation of three-dimensional unstructured grids for computational mechanics (2006)
  15. Ivanov, E. G.; Andrä, H.; Kudryavtsev, A. N.: Domain decomposition approach for automatic parallel generation of tetrahedral grids (2006)
  16. Beyer, Tilo; Schaller, Gernot; Deutsch, Andreas; Meyer-Hermann, Michael: Parallel dynamic and kinetic regular triangulation in three dimensions (2005) ioport
  17. Wu, Y.; Ozdamar, L.; Kumar, Arun: TRIOPT: A triangulation-based partitioning algorithm for global optimization (2005)
  18. Kohout, Josef; Kolingerová, Ivana: Parallel Delaunay triangulation in (E^3): make it simple (2003) ioport
  19. Kolingerová, I.: Modified DAG location for Delaunay triangulation (2002)
  20. Krysl, Petr; Ortiz, Michael: Variational Delaunay approach to the generation of tetrahedral finite element meshes (2001)

1 2 next