Comment: Algorithms for computing relative neighbourhood graph

G. T. Toussaint

Research output: Contribution to journalArticlepeer-review


Until recently no algorithm existed for computing the relative neighbourhood graph of n points on the plane in less than O(n2) worst-case time. Urquhart recently presented an O(n log n) algorithm for solving this problem. In this letter it is shown that Urquhart's algorithm does not always work and hence finding an O(n log n) algorithm remains an open problem.

Original languageEnglish (US)
Number of pages1
JournalElectronics Letters
Issue number22
StatePublished - Oct 23 1980


  • Algorithms
  • Graph theory
  • Pattern recognition

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this