An almost naive algorithm for finding relative neighbourhood graphs in Lp metrics
Authors:Jyrki Katajainen and Olli Nevalainen
Published in:Informatique Théorique et Applications 21,2 (1987), 199-215
Full text:<pdf.gif>PDF (726 kB)  
Copyright:© Gauthier-Villars
Abstract:The relative neighbourhood graph (RNG) of a set of n points in a d-dimensional space contains an edge between a particular pair (v, w) of points if in the point set there is no other point for which the larger of distances from v and w is smaller than the distance of v and w.

Let ℜpd denote the d-dimensional space with the Lp metric, 1 ≤ p ≤ ∞. A new simple algorithm for computing the RNG in ℜpd is given. It is an improved version of the O(d n2 + n3) algorithm proposed by R.B. Urquhart. In ℜp2 the worst case running time of our algorithm is O(n2.5) for 1 < p < ∞, for p = 1 or p = ∞ the worst case time is Θ(n3), and for point sets uniformly distributed in a unit square the average time is O(n2) for 1 ≤ p ≤ ∞. The demand for the storage space is O(d n + n2) and it can be reduced to O(d n + |RNG|), where |RNG| stands for the cardinality of the output, but this reduction manifolds the observed running time by a constant factor.

Related:<html.gif>HTML (Thesis)  
  author = {Jyrki Katajainen and Olli Nevalainen},
  title = {An almost naive algorithm for finding relative neighbourhood graphs
    in $L_p$ metrics},
  journaltitle = {Informatique Th\'{e}orique et Applications},
  volume = {21},
  number = {2},
  year = {1987},
  pages = {199--215},
This page was generated by Jyrki Katajainen <> on 22.05.2015.