@techreport{R-89-06,
TITLE = {Greedy Triangulation can be Efficiently Implemented in the Average Case},
AUTHOR = {Andrzej Lingas},
YEAR = {1989},
NUMBER = {R-89-06},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-89-06+abstr},
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).},
IDANR = {LiTH-IDA-R-89-06},
NOTE = {Also in Proc. of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science, Amsterdam, The Netherlands, June 1988}