Problem settings motivated by the analysis of smooth shapes which are represented by a point cloud in ℝ³ are considered. In particular, we provide algorithms for approximating the unweighted and weighted geodesic distances on an underlying smooth two-manifold embedded in a three-dimensional space and represented by a discrete input sample. Furthermore, we also consider the problem setting of medial axis approximation starting exclusively from such a point cloud. The resulting algorithm guarantees a subquadratic running time while providing a convergence guarantee for the computed approximation object.

Furthermore, we investigate the measurement of similarities defined as distances between two polygonal curves given as an input. In particular, we discuss a modified version of the so-called Fréchet distance, namely a type of a partial similarity under the Fréchet distance, and provide a polynomial time approximation algorithm guaranteeing an additive approximation error related to an input approximation parameter and the summed length of the input curves.