Partial Matching between Surfaces Using Frechet Distance

摘要

Computing the Frechet distance for surfaces is a surprisingly hard problem. We introduce a partial variant of the Frechet distance problem, which for given surfaces P and Q asks to compute a surface R C Q with minimum Frechet distance to P. Like the Frechet distance, the partial Frechet distance is NP-hard to compute between terrains and also between polygons with holes. We restrict P, Q, and R to be coplanar simple polygons. For this restricted class of surfaces, we develop a polynomial time algorithm to compute the partial Frechet distance and show that such an R C Q can be computed in polynomial time as well. This is the first algorithm to address a partial Frechet distance problem for surfaces and extends Buchin et al.'s algorithm for computing the Frechet distance between simple polygons.