The Fréchet distance is a popular distance measure for curves which naturally lends itself to fundamental computational tasks, such as clustering, nearest-neighbor searching, and spherical range searching in the corresponding metric space. However, its inherent complexity poses considerable computational challenges in practice. To address this problem we study distortion of the probabilistic embedding that results from projecting the curves to a randomly chosen line. Such an embedding could be used in combination with, e.g. locality-sensitive hashing. We show that in the worst case and under reasonable assumptions, the discrete Fréchet distance between two polygonal curves in IR 2 or IR 3 of complexity t degrades by a factor linear in t with constant probability. We show upper and lower bounds on the distortion. The Fréchet distance is a distance measure for curves which naturally lends itself to fundamental computational tasks, such as clustering, nearest-neighbor searching, and spherical range searching in the corresponding metric space. However, their inherent complexity poses considerable computational challenges in practice. Indeed, spherical range searching under the Fréchet distance was recently the topic of the yearly ACM SIGSPATIAL GISCUP competition 1 , highlighting the relevance and the difficulty of designing efficient data structures for this problem. At the same time, Afshani and Driemel show lower bounds on the space-query-tradeoff in the pointer model [1] that demonstrate that this problem is even harder than simplex-range searching. The computational complexity of computing a single Fréchet distance between two given curves is a well-studied topic [2, 6-9, 12, 15]. It is believed that it takes time that is quadratic in the length of the curves and this running time can be achieved by applying dynamic programming. In this body of literature, the case of 1-dimensional curves under the continuous Fréchet distance stands out. In particular, no lower bounds are known on computing the continuous Fréchet distance between 1-dimensional curves. It has been observed that the problem has a special structure in this case [10] . Clustering under the Fréchet distance can be done efficiently for 1-dimensional curves [13] , but seems to be harder for curves in the plane or higher dimensions. Bringmann and Künnemann use projections to lines to speed up their approximation algorithm for the Fréchet distance [8] . They show that the distance computation can be done in linear time, if the convex hulls of the two curves are disjoint. It is tempting to believe that the curves being restricted to 1-dimensional space makes the * Driemel has been supported by NWO Veni project "Clustering time series and trajectories (10019853)".
Only recently REF studied the first probabilistic embeddings of the Fréchet distance by projecting the curves on a random line.
Probabilistic Embeddings of the Fréchet Distance
ArXiv
ArXiv
Computer Science