Minimax Estimation of Distances on a Surface and Minimax Manifold Learning in the Isometric-to-Convex Setting

The estimation of shortest paths and intrinsic distances on surfaces is a fundamental problem in computational geometry with wide-ranging applications. In motion planning, shortest paths represent resource-efficient sequences of actions to be undertaken by the agent in some given configuration space [57, 56]. In addition to the clear applications to robot locomotion and manipulation, this framework has bore fruit in the field of biology wherein proteins and folding networks are of great interest [2, 76]. In cluster analysis, geodesic distances have found use as a similarity metric to create partitions that respect the underlying geometry [51, 65, 58]. In manifold learning, the Isometric Feature Mapping (Isomap) algorithm crucially depends on the approximation of geodesic distances on the underlying surface [75], and so does another important algorithm, Maximum Variance Unfolding (MVU) [79] although in disguise [64, 12]. This is closely related to the estimation of distances for the purpose of embedding a (weighted) graph (aka multidimensional scaling with missing distances), with one of the first methods suggested for that purpose being that of using the graph distances [55, 71, 70, 62].