Computing the discrete Fréchet distance with imprecise input

Hee Kap Ahn; Christian Knauer; Marc Scherfenberg; Lena Schlipf; Antoine Vigneron

doi:10.1007/978-3-642-17514-5_36

Computing the discrete Fréchet distance with imprecise input

Hee Kap Ahn^*, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2^O(d2)m²n ² log²(mn) the Fréchet distance lower bound between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log ²(mn) + (m² + n²)log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L_∞ distance, we give an O(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the Fréchet distance upper bound, as well as the smallest possible Fréchet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).

Original language	English (US)
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	422-433
Number of pages	12
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-17514-5_36
State	Published - 2010
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: Dec 15 2010 → Dec 17 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6507 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	12/15/10 → 12/17/10

Bibliographical note

Funding Information:
Work by Ahn was supported by the Korea Research Foundation Grant funded by the Korean Government(KRF-2008-614-D00008). Work by Knauer and Scher-fenberg was supported by the German Science Foundation (DFG) under grant Al 253/5-3. Work by Schlipf was supported by the Deutsche Forschungsgemein-schaft within the research training group ’Methods for Discrete Structures’(GRK 1408).

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17514-5_36

Cite this

Ahn, H. K., Knauer, C., Scherfenberg, M., Schlipf, L., & Vigneron, A. (2010). Computing the discrete Fréchet distance with imprecise input. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 2 ed., pp. 422-433). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_36

Ahn, Hee Kap ; Knauer, Christian ; Scherfenberg, Marc et al. / Computing the discrete Fréchet distance with imprecise input. Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. pp. 422-433 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{60e98e99718641478ed66d462765ff52,

title = "Computing the discrete Fr{\'e}chet distance with imprecise input",

abstract = "We consider the problem of computing the discrete Fr{\'e}chet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2O(d2)m2n 2 log2(mn) the Fr{\'e}chet distance lower bound between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log 2(mn) + (m2 + n2)log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L∞ distance, we give an O(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the Fr{\'e}chet distance upper bound, as well as the smallest possible Fr{\'e}chet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. These algorithms achieve constant factor approximation ratios in {"}realistic{"} settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).",

author = "Ahn, {Hee Kap} and Christian Knauer and Marc Scherfenberg and Lena Schlipf and Antoine Vigneron",

note = "Funding Information: Work by Ahn was supported by the Korea Research Foundation Grant funded by the Korean Government(KRF-2008-614-D00008). Work by Knauer and Scher-fenberg was supported by the German Science Foundation (DFG) under grant Al 253/5-3. Work by Schlipf was supported by the Deutsche Forschungsgemein-schaft within the research training group {\textquoteright}Methods for Discrete Structures{\textquoteright}(GRK 1408).; 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17514-5_36",

language = "English (US)",

isbn = "3642175163",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "422--433",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 2",

}

Ahn, HK, Knauer, C, Scherfenberg, M, Schlipf, L & Vigneron, A 2010, Computing the discrete Fréchet distance with imprecise input. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6507 LNCS, pp. 422-433, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 12/15/10. https://doi.org/10.1007/978-3-642-17514-5_36

Computing the discrete Fréchet distance with imprecise input. / Ahn, Hee Kap; Knauer, Christian; Scherfenberg, Marc et al.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. p. 422-433 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Computing the discrete Fréchet distance with imprecise input

AU - Ahn, Hee Kap

AU - Knauer, Christian

AU - Scherfenberg, Marc

AU - Schlipf, Lena

AU - Vigneron, Antoine

N1 - Funding Information: Work by Ahn was supported by the Korea Research Foundation Grant funded by the Korean Government(KRF-2008-614-D00008). Work by Knauer and Scher-fenberg was supported by the German Science Foundation (DFG) under grant Al 253/5-3. Work by Schlipf was supported by the Deutsche Forschungsgemein-schaft within the research training group ’Methods for Discrete Structures’(GRK 1408).

PY - 2010

Y1 - 2010

N2 - We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2O(d2)m2n 2 log2(mn) the Fréchet distance lower bound between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log 2(mn) + (m2 + n2)log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L∞ distance, we give an O(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the Fréchet distance upper bound, as well as the smallest possible Fréchet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).

AB - We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2O(d2)m2n 2 log2(mn) the Fréchet distance lower bound between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log 2(mn) + (m2 + n2)log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L∞ distance, we give an O(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the Fréchet distance upper bound, as well as the smallest possible Fréchet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).

UR - http://www.scopus.com/inward/record.url?scp=78650861075&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_36

DO - 10.1007/978-3-642-17514-5_36

M3 - Conference contribution

AN - SCOPUS:78650861075

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 422

EP - 433

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Ahn HK, Knauer C, Scherfenberg M, Schlipf L, Vigneron A. Computing the discrete Fréchet distance with imprecise input. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 ed. 2010. p. 422-433. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-17514-5_36

Computing the discrete Fréchet distance with imprecise input

Abstract

Publication series

Other

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this