[R] frechet distance

[Rajarshi Guha]

On Thu, 2006-06-22 at 19:52 -0700, Spencer Graves wrote:
> 	  RSiteSearch("Frechet distance") returned only one hit for me just 
> now, and that was for a Frechet distribution, as you mentioned.  Google 
> found "www.cs.concordia.ca/cccg/papers/39.pdf", which suggests that 
> computing it may not be easy.

In addition, from what I have read it is supposed to be NP-hard. However
my problems are usually small. 

> 1.  If you absolutely need the Frechet distance and you can describe 
> an algorithm for computing it but get stuck writing a function for it, 
> please submit another question outlining what you've tried and that 
> obstacle you've found.
> 
> 	  2.  Alternatively, you might describe the more general problem you 
> are trying to solve, why you thought the Frechet distance might help and 
> invite alternative suggestions.

I have some curves (in the form of points) which are sigmoidal. I also
have some curves which look like 2 sigmoid curves joined head to tail.
Something like


                                     -----
				    /
			           /
			     ------
		            /
			   /
			  /
		   ------

Now these curves can vary: in some cases the initial lower tail might be
truncated.  For the 'stepwise' sigmoidal curves, the middle step might
not be horizontal but inclined to some degree and so on.

My goal is to be given a set of points representing a curve and try and
identify whether it is of the standard sigmoid form or of the 'stepwise'
sigmoid form.

My plan was to generate a 'canonical sigmoid curve' via the logistic
equation and then perform a curve matching operation. Thus for a
supplied curve that is sigmoid in nature it will match the 'canonical
curve' to a better extent than would a curve that is stepwise in nature.
(The matching is performed after applying a Procrustes transformation)

Initially I tried using the Hausdorff distance, but this does not take
into account the ordering of the points in the curve and did not always
give a conclusive answer. A number of references (including the one
above) indicate that the Frechet distance is better suited for curve
matching problems.

As you noted, evaluating the Frechet distance is non-trivial and the
only code that I could find was some code that is dependent on the CGAL
(http://www.cgal.org/) library. As far as I could see, CGAL does not
have any R bindings.

An alternative that I had considered was to to evaluate the distance
matrix of the points making up the curve and then evaluating the root
mean square error of the matrix elements for the canonical curve and the
supplied curve. My initial experiments indicated that this generally
works but I observed some cases where a stepwise curve matched the
canonical sigmoid better (ie lower RMSE) than an actual sigmoid curve.

Another alternative is look at a graph of the first derivative of the
curve. A standard sigmoidal curve will result in a graph with a single
peak, a stepwise curve like above will result in a graph with 2 peaks.
Thus this could be reduced to a peak picking problem. The problem is the
curves I'll get are not smooth and can have small kinks - this leads to
(usually) quite small peaks in the graph of the first derivative - but
most of the code that has been described on this list for peak picking
also picks them up, thus making identification of the curve ambiguous.

To be honest I do not fully understand the algorithm used to evaluate
the Frechet distance hence my request for code. However, I'm not fixated
on the Frechet distance :) If there are simpler approaches I'm open to
them.

Thanks,

-------------------------------------------------------------------
Rajarshi Guha <rxg218 at psu.edu> <http://jijo.cjb.net>
GPG Fingerprint: 0CCA 8EE2 2EEB 25E2 AB04 06F7 1BB9 E634 9B87 56EE
-------------------------------------------------------------------
Q: What do you get when you cross a mosquito with a mountain climber?
A: Nothing. You can't cross a vector with a scaler.