PATHOLOGY ASSOCIATED WITH Cryptobia INFECTION IN A SUMMER FLOUNDER (Paralichthys dentatus)

Abstract

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. \nAs a positive result we show that the Fréchet distance between polygons with one hole can be computed in polynomial time.