Computing the Fréchet distance with shortcuts is NP-hard

M. Buchin, A. Driemel, B. Speckmann

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

103 Downloads (Pure)

Samenvatting

We study the shortcut Fréchet distance, a natural variant of the Fréchet distance that allows us to take shortcuts from and to any point along one of the curves. We show that, surprisingly, the problem of computing the shortcut Fréchet distance exactly is NP-hard. Furthermore, we give a 3-approximation algorithm for the decision version of the problem.
Originele taal-2Engels
Pagina's43-46
StatusGepubliceerd - 2013
Evenement29th European Workshop on Computational Geometry (EuroCG 2013) - Braunschweig, Duitsland
Duur: 17 mrt 201320 mrt 2013
Congresnummer: 29

Workshop

Workshop29th European Workshop on Computational Geometry (EuroCG 2013)
Verkorte titelEuroCG 2013
Land/RegioDuitsland
StadBraunschweig
Periode17/03/1320/03/13

Vingerafdruk

Duik in de onderzoeksthema's van 'Computing the Fréchet distance with shortcuts is NP-hard'. Samen vormen ze een unieke vingerafdruk.

Citeer dit