文章基本信息

标题：The k-FrÃ©chet Distance: How to Walk Your Dog While Teleporting
本地全文：下载
作者：Hugo Alves Akitaya ; Maike Buchin ; Leonie Ryvkin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-15
DOI：10.4230/LIPIcs.ISAAC.2019.50
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We introduce a new distance measure for comparing polygonal chains: the k-FrÃ©chet distance. As the name implies, it is closely related to the well-studied FrÃ©chet distance but detects similarities between curves that resemble each other only piecewise. The parameter k denotes the number of subcurves into which we divide the input curves (thus we allow up to k-1 "teleports" on each input curve). The k-FrÃ©chet distance provides a nice transition between (weak) FrÃ©chet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NP-hard, which is interesting since both (weak) FrÃ©chet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the k-FrÃ©chet distance: besides a short exponential-time algorithm for the general case, we give a polynomial-time algorithm for k=2, i.e., we ask that we subdivide our input curves into two subcurves each. We can also approximate the optimal k by factor 2. We then present a more intricate FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersect the epsilon-neighborhood of a point on the other curve).
关键词：Measures; FrÃ©chet distance; Hardness; FPT