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 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}}^{\ast }$ of the stretch factor obtained using an optimal placement of $k$ sources as ${\mathcal{F}}_{FPS}\le 2r_e^2{\mathcal{F}}^{\ast }+2r_e^2+8r_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.

13 pages, 4 figures

References in corpus (2)

• Geodesic Paths On 3D Surfaces: Survey and Open Problems
• Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph

Cited by in corpus (6)

• Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph
• Dynamic Point Cloud Denoising via Manifold-to-Manifold Distance
• A Self Supervised StyleGAN for Image Annotation and Classification with Extremely Limited Labels
• Training Data Set Refinement for the Machine Learning Potential of Li-Si Alloys via Structural Similarity Analysis
• High Performance Out-of-sample Embedding Techniques for Multidimensional Scaling
• Em-K Indexing for Approximate Query Matching in Large-scale ER