Computing the similarity between moving curves

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)
70 Downloads (Pure)


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.
Originele taal-2Engels
TitelProc. 23rd Annual European Symposium on Algorithms (ESA)
RedacteurenN. Bansal, I. Finocchi
ISBN van geprinte versie978-3-662-48349-7
StatusGepubliceerd - 2015
Evenement23rd Annual European Symposium on Algorithms (ESA 2015) - Patras, Griekenland
Duur: 14 sep 201516 sep 2015
Congresnummer: 23

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres23rd Annual European Symposium on Algorithms (ESA 2015)
Verkorte titelESA 2015
Internet adres


Duik in de onderzoeksthema's van 'Computing the similarity between moving curves'. Samen vormen ze een unieke vingerafdruk.

Citeer dit