  In the first part of this thesis, we consider an instance of Frechet distance
problem in which the speed of traversal along each segment of the curves is
restricted to be within a specfied 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.
  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. 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.
  As the last part of this thesis, given a point set S and a polygonal curve P
in R^d, 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.
