An O(n log n) algorithm for the all-nearest-neighbors problem (Q1115187): Difference between revisions

From MaRDI portal
Created claim: Wikidata QID (P12): Q29396159, #quickstatements; #temporary_batch_1705549208013
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multidimensional divide-and-conquer / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of finding fixed-radius near neighbors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Expected-Time Algorithms for Closest Point Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3992847 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4144192 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4164569 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 13:53, 19 June 2024

scientific article
Language Label Description Also known as
English
An O(n log n) algorithm for the all-nearest-neighbors problem
scientific article

    Statements

    An O(n log n) algorithm for the all-nearest-neighbors problem (English)
    0 references
    0 references
    0 references
    1989
    0 references
    Given a set V of n points in k-dimensional space, and an \(L_ q\)-metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each point p in V, find all those points in V-\(\{\) \(p\}\) that are closest to p under the distance metric \(L_ q\). We give an O(n log n) algorithm for the all-nearest-neighbors problem, for fixed dimension k and fixed metric \(L_ q\). Since there is an \(\Omega\) (n log n) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest- neighbors problem (for \(k=1)\), the running time of our algorithm is optimal up to a constant factor.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    computational geometry
    0 references
    Minkowski metric
    0 references
    all-nearest-neighbors problem
    0 references
    algebraic decision-tree model of computation
    0 references
    0 references