OPTIMAL DELAUNAY POINT INSERTION

BOROUCHAKI, H. ; GEORGE, P. L. ; LO, S. H.

Chichester [u.a.] : Wiley-Blackwell
Published 1996

ISSN:	0029-5981
Keywords:	Delaunay triangulation ; Voronoï tesselation ; convex hull ; Engineering ; Engineering General
Source:	Wiley InterScience Backfile Collection 1832-2000
Topics:	Mathematics Technology
Notes:	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.
Additional Material:	35 Ill.
Type of Medium:	Electronic Resource