Analysis of farthest point sampling for approximating geodesics in a graph

DOI10.1016/J.COMGEO.2016.05.005MaRDI QIDQ679744zbMATHOpenAlexFDO

Authors Pegah Kamousi, Sylvain Lazard, Anil Maheshwari, Stefanie Wuhrer

Publication date 19 January 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.4665

zbMATH Keywords

shortest pathsapproximation algorithmsplanar graphsapproximate geodesicsfarthest point sampling

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38)

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}leq2r_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.

Recommendations

• Approximating the average stretch factor of geometric graphs
• scientific article; zbMATH DE number 1809600
• Approximating the average stretch factor of geometric graphs
• Approximate Shortest Path Queries Using Voronoi Duals
• scientific article; zbMATH DE number 2119744

Cites work

• scientific article; zbMATH DE number 2089224 (Why is no real title available?)
• A note on two problems in connexion with graphs
• A survey of geodesic paths on 3D surfaces
• An approximation algorithm for the edge-dilation \(k\)-center problem.
• Approximate distance oracles for planar graphs with improved query time-space tradeoff
• Clustering to minimize the maximum intercluster distance
• Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching
• POSTURE INVARIANT CORRESPONDENCE OF INCOMPLETE TRIANGULAR MANIFOLDS
• The Rectilinear Steiner Tree Problem is $NP$-Complete

This page was built for publication: Analysis of farthest point sampling for approximating geodesics in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679744)