optimal triangulation problem

(classic problem)

Definition: Find the triangulation with the greatest overall minimum angle. There is an incremental algorithm that takes O(n log n) time.

Note: Triangulation is breaking up an area into triangles. The goal is to make all the triangles as close to equilateral as possible. Equivalently, have as few "slivers" as possible.

This is the best triangulation if you want to interpolate a height field (topographic map) between given points, or to divide a surface to triangles and research the heat conduction, etc. between them. Contributed by Motty Porat (vn16908@netvision.net.il) 10 July 2000.

See Computational Geometry by De Berg, Van Kreveld, Overmars and Schwarzkopf.

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 December 2004.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "optimal triangulation problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 17 December 2004. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/optimTriangulation.html