Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph
Identifieur interne : 000E45 ( Hal/Curation ); précédent : 000E44; suivant : 000E46Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph
Auteurs : Pegah Kamousi [Belgique] ; Sylvain Lazard [France] ; Anil Maheshwari [Canada] ; Stefanie Wuhrer [Allemagne]Source :
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.
Url:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000E45
Links to Exploration step
Hal:hal-00927643Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph</title>
<author><name sortKey="Kamousi, Pegah" sort="Kamousi, Pegah" uniqKey="Kamousi P" first="Pegah" last="Kamousi">Pegah Kamousi</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-5591" status="VALID"><orgName>Département d'Informatique [Bruxelles]</orgName>
<orgName type="acronym">ULB</orgName>
<desc><address><addrLine>Campus de la Plaine ULB CP212, boulevard du Triomphe, 1050 Bruxelles</addrLine>
<country key="BE"></country>
</address>
<ref type="url">http://www.ulb.ac.be/facs/sciences/info/</ref>
</desc>
<listRelation><relation active="#struct-92969" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-92969" type="direct"><org type="institution" xml:id="struct-92969" status="VALID"><orgName>Université Libre de Bruxelles [Bruxelles]</orgName>
<orgName type="acronym">ULB</orgName>
<desc><address><addrLine>Avenue Franklin Roosevelt 50 - 1050 Bruxelles</addrLine>
<country key="BE"></country>
</address>
<ref type="url">http://www.ulb.ac.be</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Belgique</country>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-205129" status="VALID"><idno type="RNSR">200518305E</idno>
<orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName>
<orgName type="acronym">VEGAS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/vegas</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Maheshwari, Anil" sort="Maheshwari, Anil" uniqKey="Maheshwari A" first="Anil" last="Maheshwari">Anil Maheshwari</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7738" status="VALID"><orgName>School of Computer Science [Ottawa]</orgName>
<desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine>
<country key="CA"></country>
</address>
<ref type="url">http://www.scs.carleton.ca/school/</ref>
</desc>
<listRelation><relation active="#struct-208909" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName>
<desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine>
<country key="CA"></country>
</address>
<ref type="url">http://www.carleton.ca/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Canada</country>
</affiliation>
</author>
<author><name sortKey="Wuhrer, Stefanie" sort="Wuhrer, Stefanie" uniqKey="Wuhrer S" first="Stefanie" last="Wuhrer">Stefanie Wuhrer</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-110922" status="VALID"><orgName>Saarland University [Saarbrücke]</orgName>
<desc><address><addrLine>PF 151150 66041 Saarbrücke</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.uni-saarland.de/en/</ref>
</desc>
<listRelation><relation active="#struct-365003" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-365003" type="direct"><org type="institution" xml:id="struct-365003" status="INCOMING"><orgName>SAARLAND UNIVERSITY</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Allemagne</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00927643</idno>
<idno type="halId">hal-00927643</idno>
<idno type="halUri">https://hal.inria.fr/hal-00927643</idno>
<idno type="url">https://hal.inria.fr/hal-00927643</idno>
<date when="2013-11">2013-11</date>
<idno type="wicri:Area/Hal/Corpus">000E45</idno>
<idno type="wicri:Area/Hal/Curation">000E45</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph</title>
<author><name sortKey="Kamousi, Pegah" sort="Kamousi, Pegah" uniqKey="Kamousi P" first="Pegah" last="Kamousi">Pegah Kamousi</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-5591" status="VALID"><orgName>Département d'Informatique [Bruxelles]</orgName>
<orgName type="acronym">ULB</orgName>
<desc><address><addrLine>Campus de la Plaine ULB CP212, boulevard du Triomphe, 1050 Bruxelles</addrLine>
<country key="BE"></country>
</address>
<ref type="url">http://www.ulb.ac.be/facs/sciences/info/</ref>
</desc>
<listRelation><relation active="#struct-92969" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-92969" type="direct"><org type="institution" xml:id="struct-92969" status="VALID"><orgName>Université Libre de Bruxelles [Bruxelles]</orgName>
<orgName type="acronym">ULB</orgName>
<desc><address><addrLine>Avenue Franklin Roosevelt 50 - 1050 Bruxelles</addrLine>
<country key="BE"></country>
</address>
<ref type="url">http://www.ulb.ac.be</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Belgique</country>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-205129" status="VALID"><idno type="RNSR">200518305E</idno>
<orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName>
<orgName type="acronym">VEGAS</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/vegas</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Maheshwari, Anil" sort="Maheshwari, Anil" uniqKey="Maheshwari A" first="Anil" last="Maheshwari">Anil Maheshwari</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-7738" status="VALID"><orgName>School of Computer Science [Ottawa]</orgName>
<desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine>
<country key="CA"></country>
</address>
<ref type="url">http://www.scs.carleton.ca/school/</ref>
</desc>
<listRelation><relation active="#struct-208909" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName>
<desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine>
<country key="CA"></country>
</address>
<ref type="url">http://www.carleton.ca/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Canada</country>
</affiliation>
</author>
<author><name sortKey="Wuhrer, Stefanie" sort="Wuhrer, Stefanie" uniqKey="Wuhrer S" first="Stefanie" last="Wuhrer">Stefanie Wuhrer</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-110922" status="VALID"><orgName>Saarland University [Saarbrücke]</orgName>
<desc><address><addrLine>PF 151150 66041 Saarbrücke</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.uni-saarland.de/en/</ref>
</desc>
<listRelation><relation active="#struct-365003" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-365003" type="direct"><org type="institution" xml:id="struct-365003" status="INCOMING"><orgName>SAARLAND UNIVERSITY</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Allemagne</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph</title>
<author role="aut"><persName><forename type="first">Pegah</forename>
<surname>Kamousi</surname>
</persName>
<email></email>
<idno type="halauthor">965780</idno>
<affiliation ref="#struct-5591"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Sylvain</forename>
<surname>Lazard</surname>
</persName>
<email>sylvain.lazard@inria.fr</email>
<ptr type="url" target="http://www.loria.fr/~lazard/"></ptr>
<idno type="idhal">sylvain-lazard</idno>
<idno type="halauthor">661543</idno>
<affiliation ref="#struct-205129"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Anil</forename>
<surname>Maheshwari</surname>
</persName>
<email></email>
<idno type="halauthor">965781</idno>
<affiliation ref="#struct-7738"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Stefanie</forename>
<surname>Wuhrer</surname>
</persName>
<email></email>
<idno type="idhal">stefanie-wuhrer</idno>
<idno type="halauthor">965782</idno>
<idno type="arXiv">http://arxiv.org/a/Wuhrer_S</idno>
<affiliation ref="#struct-110922"></affiliation>
</author>
<editor role="depositor"><persName><forename>Sylvain</forename>
<surname>Lazard</surname>
</persName>
<email>sylvain.lazard@inria.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-01-13 13:54:36</date>
<date type="whenModified">2015-12-16 01:10:32</date>
<date type="whenReleased">2014-01-14 12:49:59</date>
<date type="whenProduced">2013-11</date>
<date type="whenEndEmbargoed">2014-01-13</date>
<ref type="file" target="https://hal.inria.fr/hal-00927643/document"><date notBefore="2014-01-13"></date>
</ref>
<ref type="file" subtype="author" n="1" target="https://hal.inria.fr/hal-00927643/file/ShortestPaths.pdf"><date notBefore="2014-01-13"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="103314"><persName><forename>Sylvain</forename>
<surname>Lazard</surname>
</persName>
<email>sylvain.lazard@inria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">hal-00927643</idno>
<idno type="halUri">https://hal.inria.fr/hal-00927643</idno>
<idno type="halBibtex">kamousi:hal-00927643</idno>
<idno type="halRefHtml">[Research Report] INRIA. 2013, pp.13</idno>
<idno type="halRef">[Research Report] INRIA. 2013, pp.13</idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA-ACGI" p="LORIA">Algorithmique, calcul, image et géométrie</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="LORIA-ALGO-TEST5">LORIA-ALGO-TEST5 </idno>
<idno type="stamp" n="INRIA2">INRIA 2</idno>
</seriesStmt>
<notesStmt><note type="report" n="6">Research Report</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph</title>
<author role="aut"><persName><forename type="first">Pegah</forename>
<surname>Kamousi</surname>
</persName>
<idno type="halAuthorId">965780</idno>
<affiliation ref="#struct-5591"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Sylvain</forename>
<surname>Lazard</surname>
</persName>
<email>sylvain.lazard@inria.fr</email>
<ptr type="url" target="http://www.loria.fr/~lazard/"></ptr>
<idno type="idHal">sylvain-lazard</idno>
<idno type="halAuthorId">661543</idno>
<affiliation ref="#struct-205129"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Anil</forename>
<surname>Maheshwari</surname>
</persName>
<idno type="halAuthorId">965781</idno>
<affiliation ref="#struct-7738"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Stefanie</forename>
<surname>Wuhrer</surname>
</persName>
<idno type="idHal">stefanie-wuhrer</idno>
<idno type="halAuthorId">965782</idno>
<idno type="arXiv">http://arxiv.org/a/Wuhrer_S</idno>
<affiliation ref="#struct-110922"></affiliation>
</author>
</analytic>
<monogr><imprint><biblScope unit="pp">13</biblScope>
<date type="datePub">2013-11</date>
</imprint>
<authority type="institution">INRIA</authority>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><classCode scheme="halDomain" n="info.info-cg">Computer Science [cs]/Computational Geometry [cs.CG]</classCode>
<classCode scheme="halTypology" n="REPORT">Reports</classCode>
</textClass>
<abstract xml:lang="en">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.</abstract>
</profileDesc>
</hal>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000E45 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 000E45 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Hal |étape= Curation |type= RBID |clé= Hal:hal-00927643 |texte= Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |