A quadratic time algorithm for the minmax length triangulation
Edelsbrunner H, Tan T. 1993. A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. 22(3), 527–551.
Download
No fulltext has been uploaded. References only!
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Tan, Tiow
;
Tan, TiowAbstract
It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time 0(n2). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.
Publishing Year
Date Published
1993-06-01
Journal Title
SIAM Journal on Computing
Publisher
SIAM
Acknowledgement
The authors thank an anonymous referee for suggestions on the organization of this paper.
Volume
22
Issue
3
Page
527 - 551
ISSN
IST-REx-ID
Cite this
Edelsbrunner H, Tan T. A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. 1993;22(3):527-551. doi:10.1137/0222036
Edelsbrunner, H., & Tan, T. (1993). A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0222036
Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” SIAM Journal on Computing. SIAM, 1993. https://doi.org/10.1137/0222036 .
H. Edelsbrunner and T. Tan, “A quadratic time algorithm for the minmax length triangulation,” SIAM Journal on Computing, vol. 22, no. 3. SIAM, pp. 527–551, 1993.
Edelsbrunner H, Tan T. 1993. A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. 22(3), 527–551.
Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” SIAM Journal on Computing, vol. 22, no. 3, SIAM, 1993, pp. 527–51, doi:10.1137/0222036 .
Google Scholar