[R] frechet distance

[Spencer Graves]

<see inline>	

Rajarshi Guha wrote:
> 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
> 
> 
>                                      -----
> 				    /
> 			           /
> 			     ------
> 		            /
> 			   /
> 			  /
> 		   ------
> 
	  If all curves are of this form, it suggests they are continuous and 
monotonically increasing.  Is that correct?  If yes, isn't the Frechet 
distance then just the max of the distances between the two curves at 
the end points?

	  I don't see a complete proof yet, but it would seem that the 
difficulties in computing Frechet distances would come from functions 
that are not monotonic and / or discontinuous.

	  This brings me back to my second question:  What's the larger problem 
you want to solve, for which you think the Frechet distance might help?

	  Hope this helps.
	  Spencer Graves

suppose we want

> 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.
> 
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html