IEEE Computer Graphics and Applications · 1993 · 101 citations · 9 references
ComputingComputer ScienceAlgorithmsComputational GeometryData StructuresConvex HullsDelaunay TriangulationsGeometry ProcessingPoint Cloud ProcessingConvex Hull AlgorithmsDelaunay Triangulation AlgorithmsLinear ComplexityTriangulation Algorithms
An algorithm for triangulating 2-D data points that is based on a uniform grid structure and a triangulation strategy that builds triangles in a circular fashion is discussed. The triangulation strategy lets the algorithm eliminate points from the internal data structure and decreases the time used to find points to form triangles, given an edge. The algorithm has a tested linear time complexity that significantly improves on that of other methods. As a by-product, the algorithm produces the convex hull of the data set at no extra cost. Two ways to compute the convex hull using the algorithm are presented. The first is based on the edge list and the second is based on the grid structure.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
9
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations