Abstract Shape description schemes by decomposition of regions using ellipsoids as primitive elements are discussed from the viewpoints of both amount of data and degree of approximation. Two algorithms of shape decomposition are described. One aims at describing shapes approximately, and uses skeletons of a region to determine the allocation of ellipsoids inside of the region. The other is capable of describing shapes exactly by decomposing a whole region into a union of ellipsoids, and it is formulated with morphological operations. For the respective shape decomposition algorithm, a scheme of structuring a set of ellipsoids obtained as the result of shape description in a hierarchical tree is presented. These tree structures specify the priority of each ellipsoid to represent the spread of the region progressively. Then, for reducing amount of data, a subset of ellipsoids is chosen according to the order given in the tree structure, and regions are reproduced from it. To improve the degree of approximation of the reproduced shape, a scheme of fusing the scattered set of ellipsoids with density distribution functions is presented. Simulation results have shown that our schemes perform effectively both data reduction and progressive approximation of shape.