A true O(nn) algorithm for the all-k-nearest-neighbors problem

DOI10.1007/978-3-030-36412-0_29MaRDI QIDQ2180169zbMATH OpenOpenAlexFDO

Authors Hengzhao Ma, Jianzhong Li

Publication date 13 May 2020

Full work available at URL https://arxiv.org/abs/1908.00159

zbMATH Keywords

all-\(k\)-nearest-neighborscomputational geometrynearest neighbor problems

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: In this paper we examined an algorithm for the All-k-Nearest-Neighbor problem proposed in 1980s, which was claimed to have an $O(nlogn)$ upper bound on the running time. We find the algorithm actually exceeds the so claimed upper bound, and prove that it has an $Omega(n^2)$ lower bound on the time complexity. Besides, we propose a new algorithm that truly achieves the $O(nlogn)$ bound. Detailed and rigorous theoretical proofs are provided to show the proposed algorithm runs exactly in ${\displaystyle }$O(nlog{n})${\displaystyle }$ time.

Recommendations

• An O(n log n) algorithm for the all-nearest-neighbors problem
• Probabilistic analysis of an algorithm for solving the \(k\)-dimensional all-nearest-neighbors problem by projection
• scientific article; zbMATH DE number 78497
• A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee
• scientific article; zbMATH DE number 4074476

This page was built for publication: A true \(O(n\log{n})\) algorithm for the all-\(k\)-nearest-neighbors problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180169)