Computing the similarity between moving curves

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
97 Downloads (Pure)

Abstract

In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or retreating 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 generally NP-hard, 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 a relation between obstacles.

Original languageEnglish
Pages (from-to)2-14
Number of pages13
JournalComputational Geometry
Volume73
Early online date17 Jan 2017
DOIs
Publication statusPublished - Aug 2018

Keywords

  • Complex moving objects
  • Distance between surfaces
  • Fréchet distance
  • Moving curves

Fingerprint

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

Cite this