Abstract: We present a novel approach to solve the problem of segmenting a sequence of animated objects into near-rigid components based on k given poses of the same non-rigid object. We model the segmentation problem as a clustering problem in dual space and find near-rigid segments with the property that segment boundaries are located at regions of large deformation. The presented approach is asymptotically faster than previous approaches that achieve the same property and does not require any user-specified parameters. However, if desired, the user may interactively change the number of segments. We demonstrate the practical value of our approach using experiments.