An $O(n^2 \log n)$ Time Algorithm for the Minmax Angle Triangulation | Zendy

Herbert Edelsbrunner | Zendy; Tiow Seng Tan | Zendy; Roman Waupotitsch | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An $O(n^2 \log n)$ Time Algorithm for the Minmax Angle Triangulation

Author(s) -

Herbert Edelsbrunner,

Tiow Seng Tan,

Roman Waupotitsch

Publication year - 1992

Publication title -

siam journal on scientific and statistical computing

Language(s) - English

Resource type - Book series

eISSN - 2168-3417

pISSN - 0196-5204

ISBN - 0-89791-362-0

DOI - 10.1137/0913058

Subject(s) - triangulation , minimum weight triangulation , mathematics , algorithm , combinatorics , position (finance) , lexicographical order , pitteway triangulation , minimax , point set triangulation , set (abstract data type) , point (geometry) , general position , enhanced data rates for gsm evolution , space (punctuation) , delaunay triangulation , bowyer–watson algorithm , geometry , mathematical optimization , computer science , programming language , operating system , telecommunications , finance , economics

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.

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