Computes the Frechet distance between two polygonal curves in two dimensions, using the algorithm by Alt and Godau:

 Helmut Alt, Michael Godau, "Computing the Fréchet distance between two polygonal curves", International Journal of Computational Geometry and Applications 5 (1–2): 75–91, 1995.

This program first solves the decision problem by computing the free space and then checking whether the upper right corner is free, and optionally traversing through the free space in order to compute a reparameterization. The runtime of the decision procedure is O(mn), where m and n are the numbers of vertices of the input curves.



Files for Frechet distance:
   header.h           (contains include files and data structures)
   frechet.c          (contains the main program for the decision problem)
   frbinsearch.c      (implements a binary search on epsilon by calling the
                       frechet executable several times)
   processdirectoryFR (shell script that runs frbinsearch for a directory
                       of curve files)

Compile with:
   g++ -g -o frechet frechet.c
   gcc -g -o frbinsearch frbinsearch.c
   


Sample input files:
  042002022001_1.txt    (curve)
  042002022001_1.txtOUT (another curve)
  
How to run Frechet:
  Decision problem (you have to provide an epsilon, and it checks
  whether the Frechet distance is at most epsilon):

    ./frechet curve1 curve2 error -rev -tb

       -rev if 2nd curve should be reversed
       -tb if traceback should be computed (no need to turn this on;
           currently it does not output the traced back curve/map)

  For example:
    ./frechet 042002022001_1.txt 042002022001_1.txtOUT 100 -rev
    ./frbinsearch 042002022001_1.txt 042002022001_1.txtOUT -rev

  It produces the files:
         curve1FRSTDOUT -- messages printed to STDOUT by frechet
         frnotes        -- contains the filename of inputcurve and
                           the computed Frechet distance


