conference paper
A quadratic time algorithm for the minmax length triangulation
published
yes
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
Tiow
Tan
author
FOCS: Foundations of Computer Science
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.
IEEE1991San Juan, PR, United States of America
eng
32nd Annual Symposium of Foundations of Computer Science10.1109/SFCS.1991.185400
414 - 423
yes
H. Edelsbrunner, T. Tan, in:, 32nd Annual Symposium of Foundations of Computer Science, IEEE, 1991, pp. 414–423.
Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” <i>32nd Annual Symposium of Foundations of Computer Science</i>, IEEE, 1991, pp. 414–23, doi:<a href="https://doi.org/10.1109/SFCS.1991.185400">10.1109/SFCS.1991.185400</a>.
H. Edelsbrunner and T. Tan, “A quadratic time algorithm for the minmax length triangulation,” in <i>32nd Annual Symposium of Foundations of Computer Science</i>, San Juan, PR, United States of America, 1991, pp. 414–423.
Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” In <i>32nd Annual Symposium of Foundations of Computer Science</i>, 414–23. IEEE, 1991. <a href="https://doi.org/10.1109/SFCS.1991.185400">https://doi.org/10.1109/SFCS.1991.185400</a>.
Edelsbrunner H, Tan T. A quadratic time algorithm for the minmax length triangulation. In: <i>32nd Annual Symposium of Foundations of Computer Science</i>. IEEE; 1991:414-423. doi:<a href="https://doi.org/10.1109/SFCS.1991.185400">10.1109/SFCS.1991.185400</a>
Edelsbrunner, H., & Tan, T. (1991). A quadratic time algorithm for the minmax length triangulation. In <i>32nd Annual Symposium of Foundations of Computer Science</i> (pp. 414–423). San Juan, PR, United States of America: IEEE. <a href="https://doi.org/10.1109/SFCS.1991.185400">https://doi.org/10.1109/SFCS.1991.185400</a>
Edelsbrunner H, Tan T. 1991. A quadratic time algorithm for the minmax length triangulation. 32nd Annual Symposium of Foundations of Computer Science. FOCS: Foundations of Computer Science, 414–423.
40552018-12-11T12:06:40Z2022-02-28T15:51:45Z