SIAM Journal on Scientific and Statistical Computing · 1989 · 181 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometryDelaunay TriangulationsGeometric ApproximationGeometric ConstructionsGeometric OptimizationGeometry ProcessingThree-dimensional GeometryDelaunay Triangulation AlgorithmsPolynomial Time ComplexityTransformation ProcedureTriangulation AlgorithmsTriangulations
A new algorithm is presented that uses a local transformation procedure to construct a triangulation of a set of n three-dimensional points that is pseudo-locally optimal with respect to the sphere criterion. It is conjectured that this algorithm always constructs a Delaunay triangulation, and this conjecture is supported with experimental results. The empirical time complexity of this algorithm is $O(n^{{4 / 3}} )$ for sets of random points, which compares well with existing algorithms for constructing a three-dimensional Delaunay triangulation. Also presented is a modification of this algorithm for the case that local optimality is based on the max-min solid angle criterion.
9
Computing Dirichlet tessellations
Adrian Bowyer · The Computer Journal · 1981 · 1.1K citations · Full text
C. L. Lawson · Discrete Mathematics · 1972 · 227 citations
Properties of n-dimensional triangulations
C. L. Lawson · Computer Aided Geometric Design · 1986 · 183 citations