carrier image

Recursive Spoke Darts: Local Hyperplane Sampling for Delaunay and Voronoi Meshing in Arbitrary Dimensions

Ebeida, Mohamed, Ahmad Rushdi

Proceedings, 25th International Meshing Roundtable, Elsevier, Science Direct, September 26-30 2016

INTERNATIONAL
MESHING
ROUNTABLE

25th International Meshing Roundtable
Washington DC, U.S.A.
September 26-30, 2016

Mohamed Ebeida, Sandia National Laboratories, US, msebeid@sandia.gov
Ahmad Rushdi, University of Texas, Austin, US, arushdi@utexas.edu

Abstract
We introduce Recursive Spoke Darts (RSD): a recursive hyperplane sampling algorithm that exploits the full duality between Voronoi and Delaunay entities of various dimensions. Our algorithm abandons the dependence on the empty sphere principle in the generation of Delaunay simplices providing the foundation needed for scalable consistent meshing. The algorithm relies on two simple operations: line-hyperplane trimming and spherical range search. Consequently, this approach improves scalability as multiple processors can operate on different seeds at the same time. Moreover, generating consistent meshes across processors eliminates the communication needed between them, improving scalability even more. We introduce a simple tweak to the algo- rithm which makes it possible not to visit all vertices of a Voronoi cell, generating almost-exact Delaunay graphs while avoiding the natural curse of dimensionality in high dimensions.

Download Full Paper (PDF)


Contact author(s) or publisher for availability and copyright information on above referenced article