Lingas, A. (1989). Greedy Triangulation can be Efficiently Implemented in the Average Case. Technical Report LiTH-IDA-R-89-06, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc. of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science, Amsterdam, The Netherlands, June 1988. (bibtex),
Abstract: Let S be a set of n points uniformly distributed in a unit square. We show that the greedy triangulation of S can be computed in O(n log n) expected time (without bucketing). The best previously known upper-bound on the expected-time performance of an algorithm for the greedy triangulation was O(n**2).
CS Dept TR Overview