(classic problem)
Definition: Find the triangulation with the greatest overall minimum angle. There is an incremental algorithm that takes O(n log n) time.
See also optimal polygon triangulation problem.
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
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "optimal triangulation problem", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/optimTriangulation.html