Construction of three-dimensional Delaunay triangulations using local transformations
type: Item
instance of: scholarly article
title: Construction of three-dimensional Delaunay triangulations using local transformations
zbMATH Open document ID: 0729.65120
DOI: 10.1016/0167-8396(91)90038-D
author: Barry Joe
published in: Computer Aided Geometric Design
publication date: 1991-01-01T00:00:00Z
review text: For a set of points in \(R^ 3\) the problem of Delaunay triangulation is to find a set of nonoverlapping tetrahedra that fill the convex hull of the set so that no point is in the circumscribed sphere of any tetrahedron of which it is not a vertex. The author gives the pseudocode description of two programs that solve the problem by local decisions involving five points at a time and proves that the worst case time complexity is \(O(n^ 2)\) and the expected complexity for random points is O(n(log n)\({}^ 2)\).
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 14Q15
Mathematics Subject Classification ID: 32B25
zbMATH DE Number: 4205955
zbMATH Keywords: local transformations
zbMATH Keywords: Delaunay triangulation
zbMATH Keywords: worst case time complexity
zbMATH Keywords: expected complexity for random points
reviewed by: Heinrich Guggenheimer
MaRDI profile type: Publication
cites work: On the Average Number of Maxima in a Set of Vectors and Applications
cites work: An apporach to automatic three-dimensional finite element mesh generation
cites work: Q3772828
cites work: Tetrahedrizing point sets in three dimensions
cites work: Delaunay Triangular Meshes in Convex Polygons
cites work: Three-Dimensional Triangulations from Local Transformations
cites work: Q4057549
cites work: Q4194442
cites work: Properties of \(n\)-dimensional triangulations
cites work: Q3694703
cites work: A fast algorithm for constructing Delaunay triangulations in the plane
description: scientific article; zbMATH DE number 4205955