• DocumentCode
    967562
  • Title

    Comment: Algorithms for computing relative neighbourhood graph

  • Author

    Toussaint, G.T.

  • Author_Institution
    School of Computer Science McGill University, Montreal, Canada
  • Volume
    16
  • Issue
    22
  • fYear
    1980
  • Firstpage
    860
  • Lastpage
    860
  • Abstract
    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.
  • Keywords
    graph theory; pattern recognition; algorithms; relative neighbourhood graph computing;
  • fLanguage
    English
  • Journal_Title
    Electronics Letters
  • Publisher
    iet
  • ISSN
    0013-5194
  • Type

    jour

  • DOI
    10.1049/el:19800611
  • Filename
    4245383
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=967562