DeWall

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

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

1 2 next

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

1 2 next