Premium
OPTIMAL DELAUNAY POINT INSERTION
Author(s) -
BOROUCHAKI H.,
GEORGE P. L.,
LO S. H.
Publication year - 1996
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/(sici)1097-0207(19961030)39:20<3407::aid-nme5>3.0.co;2-c
Subject(s) - delaunay triangulation , chew's second algorithm , constrained delaunay triangulation , point (geometry) , computer science , mathematics , topology (electrical circuits) , geometry , combinatorics
An efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in ℝ 3 with a linear generation rate of 15 000 tetrahedra per second for randomly generated points on an HP 735 workstation.