Semi-Computability of the Frechet Distance Between Surfaces
作者： Maike Buchin , Helmut Alt
DOI:
关键词: Combinatorics 、 Monotone polygon 、 Turing machine 、 Fréchet distance 、 Decision problem 、 Computability 、 Measure (mathematics) 、 Sequence 、 Recursively enumerable language 、 Mathematics
摘要: The Frechet distance is a measure for pa- rameterized curves or surfaces. Using discrete ap- proximation, we show that triangulated surfaces it upper semi-computable, i.e., there non-halting Turing machine which produces monotone decreas- ing sequence of rationals converging to the result. It follows decision problem, whether two given lies below some speci- fied value, recursively enumerable.
eurocg.org参考文章(7)
Edwin E. Moise, Geometric Topology in Dimensions 2 and 3 ,(1977)
Klaus Weihrauch, Xizhong Zheng, Computability on continuous, lower semi-continuous and upper semi-continuous real functions Theoretical Computer Science. ,vol. 234, pp. 109- 133 ,(2000) , 10.1016/S0304-3975(98)00045-0
M. Maurice Fréchet, Sur quelques points du calcul fonctionnel Rendiconti Del Circolo Matematico Di Palermo. ,vol. 22, pp. 1- 72 ,(1906) , 10.1007/BF03018603
Helmut Alt, Michael Godau, None, COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES International Journal of Computational Geometry and Applications. ,vol. 05, pp. 75- 91 ,(1995) , 10.1142/S0218195995000064
Maurice Frechét, Sur la distance de deux surfaces Annales de la Société Polonaise de Mathématique. ,(1925)
Klaus Weihrauch, Computable Analysis ,(2000)