Can we compute the similarity between surfaces?

H. Alt, M. Buchin

    Research output: Contribution to journalArticleAcademicpeer-review

    33 Citations (Scopus)


    A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fréchet distance. Whereas efficient algorithms are known for computing the Fréchet distance of polygonal curves, the same problem for triangulated surfaces is NP-hard. Furthermore, it remained open whether it is computable at all. Using a discrete approximation, we show that it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a decreasing sequence of rationals converging to the Fréchet distance. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below a specified value, is recursively enumerable. Furthermore, we show that a relaxed version of the Fréchet distance, the weak Fréchet distance can be computed in polynomial time. For this, we give a computable characterization of the weak Fréchet distance in a geometric data structure called the Free Space Diagram.
    Original languageEnglish
    Pages (from-to)78-99
    Number of pages22
    JournalDiscrete and Computational Geometry
    Issue number1
    Publication statusPublished - 2009


    Dive into the research topics of 'Can we compute the similarity between surfaces?'. Together they form a unique fingerprint.

    Cite this