Computing the similarity between moving curves

K. Buchin; T.A.E. Ophelders; B. Speckmann

doi:10.1007/978-3-662-48350-3_77

Computing the similarity between moving curves

K. Buchin, T.A.E. Ophelders, B. Speckmann

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

3 Citations (Scopus)

70 Downloads (Pure)

Abstract

In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality.

Original language	English
Title of host publication	Proc. 23rd Annual European Symposium on Algorithms (ESA)
Editors	N. Bansal, I. Finocchi
Publisher	Springer
Pages	928-940
ISBN (Print)	978-3-662-48349-7
DOIs	https://doi.org/10.1007/978-3-662-48350-3_77
Publication status	Published - 2015
Event	23rd Annual European Symposium on Algorithms (ESA 2015) - Patras, Greece Duration: 14 Sep 2015 → 16 Sep 2015 Conference number: 23 http://algo2015.upatras.gr/esa/

Publication series

Name	Lecture Notes in Computer Science
Volume	9294
ISSN (Print)	0302-9743

Conference

Conference	23rd Annual European Symposium on Algorithms (ESA 2015)
Abbreviated title	ESA 2015
Country/Territory	Greece
City	Patras
Period	14/09/15 → 16/09/15
Internet address	http://algo2015.upatras.gr/esa/

Access to Document

10.1007/978-3-662-48350-3_77

moving_curvesFinal author version , 509 KB

Cite this

@inproceedings{aba90458dbf24042b1b15a815f8ae3fc,

title = "Computing the similarity between moving curves",

abstract = "In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fr{\'e}chet distance between surfaces. While the Fr{\'e}chet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality.",

author = "K. Buchin and T.A.E. Ophelders and B. Speckmann",

year = "2015",

doi = "10.1007/978-3-662-48350-3_77",

language = "English",

isbn = "978-3-662-48349-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "928--940",

editor = "N. Bansal and I. Finocchi",

booktitle = "Proc. 23rd Annual European Symposium on Algorithms (ESA)",

address = "Germany",

note = "23rd Annual European Symposium on Algorithms (ESA 2015), ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

url = "http://algo2015.upatras.gr/esa/",

}

Buchin, K , Ophelders, TAE & Speckmann, B 2015, Computing the similarity between moving curves. in N Bansal & I Finocchi (eds), Proc. 23rd Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 9294, Springer, pp. 928-940, 23rd Annual European Symposium on Algorithms (ESA 2015), Patras, Greece, 14/09/15. https://doi.org/10.1007/978-3-662-48350-3_77

Computing the similarity between moving curves. / Buchin, K.; Ophelders, T.A.E.; Speckmann, B.

Proc. 23rd Annual European Symposium on Algorithms (ESA). ed. / N. Bansal; I. Finocchi. Springer, 2015. p. 928-940 (Lecture Notes in Computer Science; Vol. 9294).

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

TY - GEN

T1 - Computing the similarity between moving curves

AU - Buchin, K.

AU - Ophelders, T.A.E.

AU - Speckmann, B.

N1 - Conference code: 23

PY - 2015

Y1 - 2015

N2 - In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality.

AB - In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality.

U2 - 10.1007/978-3-662-48350-3_77

DO - 10.1007/978-3-662-48350-3_77

M3 - Conference contribution

SN - 978-3-662-48349-7

T3 - Lecture Notes in Computer Science

SP - 928

EP - 940

BT - Proc. 23rd Annual European Symposium on Algorithms (ESA)

A2 - Bansal, N.

A2 - Finocchi, I.

PB - Springer

T2 - 23rd Annual European Symposium on Algorithms (ESA 2015)

Y2 - 14 September 2015 through 16 September 2015

ER -

Computing the similarity between moving curves

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this