Analysis of a Hierarchical Clustering Algorithm in the Generation of Continuous Level of Detail

Given a polygonal model of some geometric object, a continuous level of detail system should facilitate the generation of approximations to the model at arbitrary levels of detail. In polygonal models, areas of concentrated vertices are used to describe ne detail. A Hierarchical Clustering Algorithm exploits this by [removing] these ne details rst. The Hierarchical Clustering Algorithm is one of many approaches to the continuous level of detail problem. Implementations of this algorithm are [hamstrung] by the necessity to determine the closest pair of clusters at each stage of the creation of the hierarchy. This task proves very computationally expensive when dealing with typical 3D models with thousands of vertices. Several methods of retrieving the closest pair in large data sets have been developed [and some are tested in this paper]