Approximate Star-Shaped Decomposition of Point Set Data

Abstract

Simplification or decomposition is a common strategy to handle large geometric models, which otherwise require excessive computation to process. Star-shaped decomposition partitions a model into a set of star-shaped components. A model is star shaped if and only if there exists at least one point which can see all the points of the model. Due to this interesting property, decomposing a model into star-shaped components can be used for computing camera locations to guard a given environment (the art-gallery problem), skeleton extraction, point data compression, as well as motion planning. In this paper, we propose a simple method to partition (or cluster) point set data (PSD) into 'approximately star-shaped' components. Our method can be applied to both 2D and 3D PSD and can be naturally extended to higher dimensional spaces. Our method does not require or compute any connectivity information of the input points. The proposed method only requires the position and the outward normals of points. Our experimental results show that the size of the final decomposition is close to optimal.