A hierarchical structure for surface approximation


Hierarchical triangulation is a method for point selection and surface representation where the surface is approximated at successively finer levels of detail by triangular patches whose projections in the horizontal plane are nested. A tree data structure for this representation can be constructed in O(n2) worst case and O(n log n) average case time, where n is the number of data points considered. Efficient algorithms for approximation of the elevation of an arbitrary point, contour extraction, and conversion of the hierarchical structure into an ordinary triangulated irregular network, are demonstrated. The convergence and the optimality of the approximation and the relationship of the hierarchical triangulation to a structured graph representation are examined.

Computers & Graphics