Computing the similarity between moving curves

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationProc. 23rd Annual European Symposium on Algorithms (ESA)
EditorsN. Bansal, I. Finocchi
PublisherSpringer
Pages928-940
ISBN (Print)978-3-662-48349-7
DOIs
Publication statusPublished - 2015
Event23rd Annual European Symposium on Algorithms (ESA 2015) - Patras, Greece
Duration: 14 Sep 201516 Sep 2015
Conference number: 23
http://algo2015.upatras.gr/esa/

Publication series

NameLecture Notes in Computer Science
Volume9294
ISSN (Print)0302-9743

Conference

Conference23rd Annual European Symposium on Algorithms (ESA 2015)
Abbreviated titleESA 2015
CountryGreece
CityPatras
Period14/09/1516/09/15
Internet address

Fingerprint Dive into the research topics of 'Computing the similarity between moving curves'. Together they form a unique fingerprint.

  • Cite this

    Buchin, K., Ophelders, T. A. E., & Speckmann, B. (2015). Computing the similarity between moving curves. In N. Bansal, & I. Finocchi (Eds.), Proc. 23rd Annual European Symposium on Algorithms (ESA) (pp. 928-940). (Lecture Notes in Computer Science; Vol. 9294). Springer. https://doi.org/10.1007/978-3-662-48350-3_77