A Quadratic Time Algorithm for the Minmax Length Triangulation | Zendy

Herbert Edelsbrunner | Zendy; Tiow Seng Tan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Quadratic Time Algorithm for the Minmax Length Triangulation

Author(s) -

Herbert Edelsbrunner,

Tiow Seng Tan

Publication year - 1993

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0222036

Subject(s) - minimax , triangulation , minimum weight triangulation , quadratic equation , mathematics , algorithm , computer science , combinatorics , mathematical optimization , delaunay triangulation , constrained delaunay triangulation , geometry

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(n^2 )$. 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research