Analysis of farthest point sampling for approximating geodesics in a graph

DOI10.1016/J.COMGEO.2016.05.005zbMATH Open1380.05036arXiv1311.4665OpenAlexW1658042064MaRDI QIDQ679744FDOQ679744

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

Publication date: 19 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

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}^{*}$ of the stretch factor obtained using an optimal placement of $k$ sources as $mathcal{F}_{FPS}leq2r_e^{2}mathcal{F}^{*}+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.

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

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

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)

Cites Work

• A note on two problems in connexion with graphs
• Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching
• Clustering to minimize the maximum intercluster distance
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• A survey of geodesic paths on 3D surfaces
• POSTURE INVARIANT CORRESPONDENCE OF INCOMPLETE TRIANGULAR MANIFOLDS
• Title not available (Why is that?)
• An approximation algorithm for the edge-dilation \(k\)-center problem.

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)