A quadratic time algorithm for the minmax length triangulation

H. Edelsbrunner, T. Tan, in:, IEEE, 1991, pp. 414–423.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
Abstract
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 O(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
1991-12-01
Page
414 - 423
Conference
FOCS: Foundations of Computer Science
IST-REx-ID

Cite this

Edelsbrunner H, Tan T. A quadratic time algorithm for the minmax length triangulation. In: IEEE; 1991:414-423. doi:10.1109/SFCS.1991.185400
Edelsbrunner, H., & Tan, T. (1991). A quadratic time algorithm for the minmax length triangulation (pp. 414–423). Presented at the FOCS: Foundations of Computer Science, IEEE. https://doi.org/10.1109/SFCS.1991.185400
Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation,” 414–23. IEEE, 1991. https://doi.org/10.1109/SFCS.1991.185400.
H. Edelsbrunner and T. Tan, “A quadratic time algorithm for the minmax length triangulation,” presented at the FOCS: Foundations of Computer Science, 1991, pp. 414–423.
Edelsbrunner H, Tan T. 1991. A quadratic time algorithm for the minmax length triangulation. FOCS: Foundations of Computer Science 414–423.
Edelsbrunner, Herbert, and Tiow Tan. A Quadratic Time Algorithm for the Minmax Length Triangulation. IEEE, 1991, pp. 414–23, doi:10.1109/SFCS.1991.185400.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar