Author(s):

Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman

Article Title: 
An O(n^2 log n) time algorithm for the MinMax angle triangulation

Affiliation 

Abstract: 
It is shown 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). The algorithm is fairly easy to implement and is based on the edgeinsertion scheme that iteratively improves an arbitrary initial triangulation. It can be extended to the case where edges are prescribed, and, within the same time and spacebounds, it can lexicographically minimize the sorted angle vector if the point set is in general position. Experimental results on the efficiency of the algorithm and the quality of the triangulations obtained are included.

Keywords: 
computational geometry; Triangulations; Two dimensions; minmax angle criterion; iterative improvement; edge insertion

Journal Title:

SIAM Journal on Scientific Computing

Volume: 
13

Issue 
4

ISSN:

10957197

Publisher:

Society for Industrial and Applied Mathematics

Date Published:

19920701

Start Page: 
994

End Page:

1008

DOI: 
10.1137/0913058

Open access: 
no 