An O(n^2 log n) time algorithm for the MinMax angle triangulation

H. Edelsbrunner, T. Tan, R. Waupotitsch, SIAM Journal on Scientific Computing 13 (1992) 994–1008.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
It is shown that a triangulation of a set of n points in the plane that minimizes the maximum angle can be computed in time O(n2 log n) and space O(n). The algorithm is fairly easy to implement and is based on the edge-insertion scheme that iteratively improves an arbitrary initial triangulation. It can be extended to the case where edges are prescribed, and, within the same time- and space-bounds, it can lexicographically minimize the sorted angle vector if the point set is in general position. Experimental results on the efficiency of the algorithm and the quality of the triangulations obtained are included.
Publishing Year
Date Published
1992-07-01
Journal Title
SIAM Journal on Scientific Computing
Volume
13
Issue
4
Page
994 - 1008
IST-REx-ID

Cite this

Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. 1992;13(4):994-1008. doi:10.1137/0913058
Edelsbrunner, H., Tan, T., & Waupotitsch, R. (1992). An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing, 13(4), 994–1008. https://doi.org/10.1137/0913058
Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” SIAM Journal on Scientific Computing 13, no. 4 (1992): 994–1008. https://doi.org/10.1137/0913058.
H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2 log n) time algorithm for the MinMax angle triangulation,” SIAM Journal on Scientific Computing, vol. 13, no. 4, pp. 994–1008, 1992.
Edelsbrunner H, Tan T, Waupotitsch R. 1992. An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. 13(4), 994–1008.
Edelsbrunner, Herbert, et al. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” SIAM Journal on Scientific Computing, vol. 13, no. 4, Society for Industrial and Applied Mathematics , 1992, pp. 994–1008, doi:10.1137/0913058.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar