Computing the Similarity Between Moving Curves
| Autor: | Buchin, K., Ophelders, T.A.E., Speckmann, B., Bansal, N., Finocchi, I. |
|---|---|
| Přispěvatelé: | Algorithms, Algorithms, Geometry and Applications, Applied Geometric Algorithms |
| Rok vydání: | 2015 |
| Předmět: |
Surface (mathematics)
Fréchet distance Mathematical analysis Duality (optimization) Context (language use) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Similarity (network science) 010201 computation theory & mathematics Position (vector) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Focus (optics) Simple polygon Mathematics |
| Zdroj: | Algorithms-ESA 2015 ISBN: 9783662483497 ESA Proc. 23rd Annual European Symposium on Algorithms (ESA), 928-940 STARTPAGE=928;ENDPAGE=940;TITLE=Proc. 23rd Annual European Symposium on Algorithms (ESA) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|