An O(n2log n) time algorithm for the MinMax angle triangulation
| Autor: | Herbert Edelsbrunner, Tiow-Seng Tan, Roman Waupotitsch |
|---|---|
| Rok vydání: | 1990 |
| Předmět: |
Spacetime
Plane (geometry) Triangulation (social science) Binary logarithm Minimax Space (mathematics) Minimum-weight triangulation Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Point set triangulation Algorithm Computer Science::Databases MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Symposium on Computational Geometry |
| DOI: | 10.1145/98524.98535 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|