A linear expected-time algorithm for computing planar relative neighbourhood graphs
Authors:Jyrki Katajainen, Olli Nevalainen, and Jukka Teuhola
Published in:Information Processing Letters 25,2 (1987), 77-86
Full text:<pdf.gif>PDF (659 kB)  
Copyright:© Elsevier Science Publishers B.V.
Abstract:A new algorithm for computing the relative neighbourhood graph (RNG) of a planar point set is given. The expected running time of the algorithm is linear for a point set in a unit square when the points have been generated by a homogeneous planar Poisson point process. The worst-case running time is quadratic on the number of the points. The algorithm proceeds in two steps. First, a supergraph of the RNG is constructed with the aid of a cell organization of the points. Here, a point is connected by an edge to some of its nearest neighbours in eight regions around the point. The nearest region neighbours are chosen in a special way to minimize the costs. Second, extra edges are pruned from the graph by a simple scan.
Related:<html.gif>HTML (Thesis)  
  author = {Jyrki Katajainen and Olli Nevalainen and Jukka Teuhola},
  title = {A linear expected-time algorithm for computing planar relative
    neighbourhood graphs},
  journaltitle = {Information Processing Letters},
  volume = {25},
  number = {2},
  year = {1987},
  pages = {77--86},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 22.05.2015.