A fast, space-efficient average-case algorithm for the 'Greedy' Triangulation of a point set, and a proof that the Greedy Triangulation is not approximately optimalThe paper addresses the problem of how to find the Greedy Triangulation (GT) efficiently in the average case. It is noted that the problem is open whether there exists an efficient approximation algorithm to the Optimum Triangulation. It is first shown how in the worst case, the GT may be obtained in time O(n to the 3) and space O(n). Attention is then given to how the algorithm may be slightly modified to produce a time O(n to the 2), space O(n) solution in the average case. Finally, it is mentioned that Gilbert has found a worst case solution using totally different techniques that require space O(n to the 2) and time O(n to the 2 log n).
Document ID
19800028563
Acquisition Source
Legacy CDMS
Document Type
Conference Proceedings
Authors
Manacher, G. K. (Illinois, University Chicago, Ill., United States)
Zobrist, A. L. (California Institute of Technology, Jet Propulsion Laboratory, Pasadena Calif., United States)
Date Acquired
August 10, 2013
Publication Date
January 1, 1979
Subject Category
Earth Resources And Remote Sensing
Meeting Information
Meeting: Annual Allerton Conference on Communication, Control and Computing