A True O(n logn) Algorithm for the All-k-Nearest-Neighbors Problem

2019/08/01 by Hengzhao Ma, Ma, Hengzhao, Jianzhong Li +1
Computer Science · Engineering · #Automated Road and Building Extraction #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1908.00159

openalex publication_date 2019/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Ω(n²) 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 O(nlogn) time.

Related

• A Sub-linear Time Algorithm for Approximating k-Nearest-Neighbor with Full Quality Guarantee
• An Algorithm for Reducing Approximate Nearest Neighbor to Approximate Near Neighbor with O(logn) Query Time
• Efficient Distributed Algorithms for the K-Nearest Neighbors Problem
• Computing the k Nearest-Neighbors for all Vertices via Dijkstra
• The k-Dimensional Weisfeiler-Leman Algorithm