Skip to Main content Skip to Navigation
Journal articles

Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph

Pegah Kamousi 1 Sylvain Lazard 2 Anil Maheshwari 3 Stefanie Wuhrer 4
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
4 MORPHEO [2011-2015] - Capture and Analysis of Shapes in Motion [2011-2015]
Grenoble INP [2007-2019] - Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019], LJK [2007-2015] - Laboratoire Jean Kuntzmann [2007-2015], Inria Grenoble - Rhône-Alpes
Abstract : A standard way to approximate the distance between two vertices $p$ and $q$ in a graph is to compute 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 yields an efficient computation of approximate distances between any two vertices. One standard method for choosing $k$ sources 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}_{\text{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}_{\text{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}_{\text{FPS}}\leq 2 r_e^2 \mathcal{F}^\ast+ 2 r_e^2 + 8 r_e + 1$, where $r_e$ is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor $r_e$ is not an artefact of the analysis by providing a class of graphs for which $\mathcal{F}_{\text{FPS}} \geq \frac{1}{2} r_e \mathcal{F}^\ast$.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01297624
Contributor : Sylvain Lazard <>
Submitted on : Monday, April 4, 2016 - 3:25:31 PM
Last modification on : Monday, July 20, 2020 - 9:18:59 AM
Document(s) archivé(s) le : Monday, November 14, 2016 - 4:15:55 PM

File

ShortestPaths_final.pdf
Files produced by the author(s)

Identifiers

Citation

Pegah Kamousi, Sylvain Lazard, Anil Maheshwari, Stefanie Wuhrer. Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph. Computational Geometry, Elsevier, 2016, 57, pp.1-7. ⟨10.1016/j.comgeo.2016.05.005⟩. ⟨hal-01297624v1⟩

Share

Metrics

Record views

50

Files downloads

28