(1+ε)-ANN Data Structure for Curves via Subspaces of Bounded Doubling Dimension
We consider the (1 + ε)-Approximate Nearest Neighbour (ANN) Problem for polygonal curves in d-dimensional space consisting of at most k vertices under the Fréchet distance and ask to what extent known data structures for doubling spaces can be applied to this problem. Initially, this approach does not seem viable, since the doubling dimension of the target space is known to be unbounded - even for well-behaved polygonal curves of constant complexity in one dimension. In order to overcome this, we identify a subspace of curves which has bounded doubling dimension and small Gromov-Hausdorff distance to the target space.
We then apply state-of-the-art techniques for doubling spaces and show how to obtain a data structure for the (1 + ε)-ANN problem for any set of parametrized polygonal curves. The expected preprocessing time needed to construct the data-structure is F(d, k, S, ε)n log n and the space used is F(d, k, S, ε)n, with a query time of F(d, k, S, ε)log n + F(d, k, S, ε)-log(ε), where F(d, k, S, ε) = O(2O(d)kΦ(S)ε-1)k and Φ(S) denotes the spread of the set of vertices and edges of the curves in S. We extend these results to the realistic class of c-packed curves and show improved bounds for small values of c.
How to Cite
Copyright (c) 2023 Jacobus Conradi, Anne Driemel, Benedikt Kolbe
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).