Fréchet distance of surfaces: Some simple hard cases

K. Buchin, M. Buchin, A. Schulz

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

17 Citaten (Scopus)
9 Downloads (Pure)


We show that it is NP-hard to decide the Fréchet distance between (i) non-intersecting polygons with holes embedded in the plane, (ii) 2d terrains, and (iii) self-intersecting simple polygons in 2d, which can be unfolded in 3d. The only previously known NP-hardness result for 2d surfaces was based on self-intersecting polygons with an unfolding in 4d. In contrast to this old result, our NP-hardness reductions are substantially simpler. As a positive result we show that the Fréchet distance between polygons with one hole can be computed in polynomial time.
Originele taal-2Engels
TitelAlgorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II)
RedacteurenM. Berg, de, U. Meyer
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-15780-6
StatusGepubliceerd - 2010

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Fréchet distance of surfaces: Some simple hard cases'. Samen vormen ze een unieke vingerafdruk.

Citeer dit