2026-07-24T11:17:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7818 2024-03-06T10:41:15Z ddc:004 open_access

Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats Agarwal, Pankaj K. Rubin, Natan Sharir, Micha Approximate nearest neighbor search k-flats Polyhedral distance functions Linear programming queries We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k<d, and where, for each query point q, we want to return an input flat whose distance from q is at most (1 + epsilon) times the shortest such distance, where epsilon > 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also provide a tradeoff between storage and query time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Natan Rubin and Micha Sharir 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.4 urn:nbn:de:0030-drops-78182 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode