Can we Compute the Similarity Between Surfaces?

Details Can we Compute the Similarity Between Surfaces? Can we Compute the Similarity Between Surfaces?

2007-03-02

arxiv.org/abs/cs/0703011v1

Computer Science

Computational Geometry

Scientific paper

A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fr\'echet distance. Whereas efficient algorithms are known for computing the Fr\'echet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Here, using a discrete approximation we show that it is {\em upper semi-computable}, i.e., there is a non-halting Turing machine which produces a monotone decreasing sequence of rationals converging to the result. It follows that the decision problem, whether the Fr\'echet distance of two given surfaces lies below some specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the problem, the computation of the {\em weak Fr\'echet distance} can be solved in polynomial time. For this, we give a computable characterization of the weak Fr\'echet distance in a geometric data structure called the {\em free space diagram}.

Affiliated with

Also associated with

No associations

Rating

Can we Compute the Similarity Between Surfaces? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Can we Compute the Similarity Between Surfaces?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Can we Compute the Similarity Between Surfaces? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284504