Homotopy-preserving power shape simplification

Abstract

The power shape is an approximation of the medial axis produced by the power crust algorithm. Given a sufficiently good sampling from an object, the power shape is proven to be geometrically close to its medial axis and homotopy equivalent to the object. However it tends to be very complicated and unstable to be useful in practice, so usually a simplification process is required. Thus a simplification algorithm was proposed but it requires a time-consuming regular triangulation computation and does not guarantee the preservation of the homotopy type. In this thesis, we propose a power shape simplification algorithm which guarantees the preservation of the homotopy type. Moreover, our algorithm is efficient because it only requires one traversal of the cells without the regular triangulation computation.