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.
|Titel||Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II)|
|Redacteuren||M. Berg, de, U. Meyer|
|Plaats van productie||Berlin|
|ISBN van geprinte versie||978-3-642-15780-6|
|Status||Gepubliceerd - 2010|
|Naam||Lecture Notes in Computer Science|
|ISSN van geprinte versie||0302-9743|