{'fraction_non_alphanumeric': 0.033179012345679014, 'fraction_numerical': 0.0023148148148148147, 'mean_word_length': 4.764444444444444, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The k-Fréchet Distance: How to Walk Your Dog While Teleporting

We introduce a new distance measure for comparing polygonal chains: the k-Frechet distance. As the name implies, it is closely related to the well-studied Frechet 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-Frechet distance provides a nice transition between (weak) Frechet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NP-hard, which is interesting since both (weak) Frechet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the k-Frechet 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).