Bounded Approximations of Geodesics for Triangular Manifolds with Partially Missing Data

In this paper we present an algorithm to compute approximate geodesic distances on a triangular manifold S containing n vertices with partially missing data. The proposed method computes an approximation of the geodesic distance between two vertices pi and pj on S and provides a maximum relative error bound of the approximation. The error bound is shown to be worst-case optimal. The algorithm approximates the geodesic distance without trying to reconstruct the missing data by embedding the surface in a low dimensional space via multi-dimensional scaling (MDS). We derive a new method to add an object to the embedding computed via least-squares MDS.Dans cet article, nous pr\ue9sentons un algorithme pour calculer les distances g\ue9od\ue9siques approximatives sur un ensemble triangulaire S, contenant n sommets avec des donn\ue9es partiellement manquantes. La m\ue9thode propos\ue9e calcule la distance g\ue9od\ue9sique approximative entre deux sommets pi et pj de S, avec une marge d'erreur relative maximale pour l'approximation. La marge d'erreur est indiqu\ue9e comme \ue9tant la marge optimale la plus pessimiste. L'algorithme calcule approximativement la distance g\ue9od\ue9sique, sans essayer de reconstruire les donn\ue9es manquantes, en int\ue9grant la surface dans un espace de faible dimension, au moyen du cadrage multidimensionnel (MDS - multi-dimensional scaling). Nous \ue9laborons une nouvelle m\ue9thode pour ajouter un objet \ue0 l'int\ue9gration, calcul\ue9 au moyen du MDS des moindres carr\ue9s.NRC publication: Ye