2007/03/02 by Helmut Alt, Alt, Helmut, Maike Buchin +1
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Digital Image Processing Techniques #F.1.1 #F.2.2 #FOS: Computer and information sciences #Morphological variations and asymmetry #Topological and Geometric Data Analysis #cs.CC #cs.CG
paper · pdf · doi:10.48550/arxiv.cs/0703011
arxiv created 2007/03/02 · openalex publication_date 2007/03/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. 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échet 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échet distance can be solved in polynomial time. For this, we give a computable characterization of the weak Fréchet distance in a geometric data structure called the \em free space diagram.