Applied similarity problems using Frechet distance.

摘要

The Frechet distance is a well-known metric to measure similarity of polygonal curves. In the first part of this thesis, we introduce a new metric called Frechet distance with speed limits and provide efficient algorithms for computing it. The classical Frechet distance between two curves corresponds to the maximum distance between two point objects that traverse the curves with arbitrary non-negative speeds. We consider a problem instance in which the speed of traversal along each segment of the curves is restricted to be within a specified range. This setting is more realistic than the classical Frechet distance setting, specially in GIS applications. We also study this problem in the setting where the polygonal curves are inside a simple polygon.;As the last part of this thesis, given a point set S and a polygonal curve P in Rd, we study the problem of finding a polygonal curve Q through S, which has a minimum Frechet distance to P. Furthermore, if the problem requires that curve Q visits every point in S, we show it is NP-complete.;In the second part of this thesis, we present a data structure, called the free-space map, that enables us to solve several variants of the Frechet distance problem efficiently. Back in 1995, a data structure was introduced by Alt and Godau, called the free space diagram, for computing Frechet distance. That data structure is widely used in different applications involving the Frechet distance. Our data structure encapsulates all the information available in the free-space diagram, yet it is capable of answering more general type of queries efficiently. Given that the free-space map has the same size and construction time as the standard free-space diagram, it can be viewed as a powerful alternative to it. As part of the results in Part II of the thesis, we exploit the free-space map to improve the long-standing bound for computing the partial Frechet distance and obtain improved algorithms for computing the Frechet distance between two closed curves, and the so-called minimum/maximum walk problem. We also improve the map matching algorithm for the case when the map is a directed acyclic graph.