Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph

Abstract : A standard way to approximate the distance between any two vertices $p$ and $q$ on a mesh is to compute, in the associated graph, a shortest path from $p$ to $q$ that goes through one of $k$ sources, which are well-chosen vertices. Precomputing the distance between each of the $k$ sources to all vertices of the graph yields an efficient computation of approximate distances between any two vertices. One standard method for choosing $k$ sources, which has been used extensively and successfully for isometry-invariant surface processing, is the so-called {\it Farthest Point Sampling} (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources. In this paper, we analyze the stretch factor $\mathcal{F}_{FPS}$ of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that $\mathcal{F}_{FPS}$ can be bounded in terms of the minimal value $\mathcal{F}^*$ of the stretch factor obtained using an optimal placement of $k$ sources as $\mathcal{F}_{FPS}\leq 2 r_e^2 \mathcal{F}^*+ 2 r_e^2 + 8 r_e + 1$, where $r_e$ is the ratio of the lengths of the longest and the shortest edges of the graph. This provides some evidence explaining why farthest point sampling has been used successfully for isometry-invariant shape processing. Furthermore, we show that it is NP-complete to find $k$ sources that minimize the stretch factor.
Type de document :
Rapport
[Research Report] INRIA. 2013, pp.13
Liste complète des métadonnées


https://hal.inria.fr/hal-00927643
Contributeur : Sylvain Lazard <>
Soumis le : lundi 13 janvier 2014 - 13:54:36
Dernière modification le : jeudi 22 septembre 2016 - 14:31:22
Document(s) archivé(s) le : dimanche 13 avril 2014 - 22:55:09

Fichier

ShortestPaths.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00927643, version 1

Collections

Citation

Pegah Kamousi, Sylvain Lazard, Anil Maheshwari, Stefanie Wuhrer. Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph. [Research Report] INRIA. 2013, pp.13. <hal-00927643>

Partager

Métriques

Consultations de
la notice

251

Téléchargements du document

298