Approximating solid objects by ellipsoid-tree

This paper presents an algorithm to approximate a solid model by a hierarchical set of bounding ellipsoids having optimal shape and volume approximation errors. The ellipsoid-tree is constructed in a top-down splitting framework. Starting from the root of hierarchy the volume occupied by a given model is divided into k sub-volumes where each is approximated by a volume bounding ellipsoid and will be later subdivided into k ellipsoids for the next level in hierarchy. The difficulty for implementing this algorithm comes from how to evaluate the volume of an ellipsoid outside the given model effectively and efficiently (i.e., the outside-volume-error). A new method - analytical computation based - is presented in this paper to compute the outside-volume-error. One application of ellipsoid-tree approximation has also been given at the end of the paper.