ALGORITHMS FOR COMPUTING RELATIVE NEIGHBOURHOOD GRAPH.

G. T. Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

Until recently no algorithm existed for computing the relative neighborhood graph of n points on the plane in less than O(n**2) worst-case time. R. B. Urquhart recently presented an O(n log n) algorithm or solving this problem. It is shown that Urquhart's algorithm does not always work and hence finding an O(n log n) algorithm remains an open problem. A response by R. B. Urquhart is included.

Original languageEnglish (US)
JournalElectronics Letters
Volume16
Issue number22
StatePublished - 1980

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'ALGORITHMS FOR COMPUTING RELATIVE NEIGHBOURHOOD GRAPH.'. Together they form a unique fingerprint.

Cite this