IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Sat, 30 Aug 2014 16:13:57

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).


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>