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

H. Edelsbrunner, T. Tan, R. Waupotitsch, in:, ACM, 1990, pp. 44–52.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Abstract
We show 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). In the same amount of time and space we can also handle the constrained case where edges are prescribed. The algorithm iteratively improves an arbitrary initial triangulation and is fairly easy to implement.
Publishing Year
Date Published
1990-01-01
Page
44 - 52
Conference
SCG: Symposium on Computational Geometry
IST-REx-ID

Cite this

Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2log n) time algorithm for the MinMax angle triangulation. In: ACM; 1990:44-52. doi:10.1145/98524.98535
Edelsbrunner, H., Tan, T., & Waupotitsch, R. (1990). An O(n^2log n) time algorithm for the MinMax angle triangulation (pp. 44–52). Presented at the SCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/98524.98535
Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2log n) Time Algorithm for the MinMax Angle Triangulation,” 44–52. ACM, 1990. https://doi.org/10.1145/98524.98535.
H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2log n) time algorithm for the MinMax angle triangulation,” presented at the SCG: Symposium on Computational Geometry, 1990, pp. 44–52.
Edelsbrunner H, Tan T, Waupotitsch R. 1990. An O(n^2log n) time algorithm for the MinMax angle triangulation. SCG: Symposium on Computational Geometry 44–52.
Edelsbrunner, Herbert, et al. An O(N^2log n) Time Algorithm for the MinMax Angle Triangulation. ACM, 1990, pp. 44–52, doi:10.1145/98524.98535.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar