Comment: Algorithms for computing relative neighbourhood graph

G. T. Toussaint

doi:10.1049/el:19800611

Comment: Algorithms for computing relative neighbourhood graph

G. T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Until recently no algorithm existed for computing the relative neighbourhood graph of n points on the plane in less than O(n²) 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 language	English (US)
Pages (from-to)	860
Number of pages	1
Journal	Electronics Letters
Volume	16
Issue number	22
DOIs	https://doi.org/10.1049/el:19800611
State	Published - Oct 23 1980

Keywords

Algorithms
Graph theory
Pattern recognition

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1049/el:19800611

Cite this

@article{5d210c5f91c842fd8a031388c3e2c05b,

title = "Comment: Algorithms for computing relative neighbourhood graph",

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 = "Algorithms, Graph theory, Pattern recognition",

author = "Toussaint, {G. T.}",

year = "1980",

month = oct,

day = "23",

doi = "10.1049/el:19800611",

language = "English (US)",

volume = "16",

pages = "860",

journal = "Electronics Letters",

issn = "0013-5194",

publisher = "John Wiley & Sons Inc.",

number = "22",

}

TY - JOUR

T1 - Comment

T2 - Algorithms for computing relative neighbourhood graph

AU - Toussaint, G. T.

PY - 1980/10/23

Y1 - 1980/10/23

N2 - 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.

AB - 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.

KW - Algorithms

KW - Graph theory

KW - Pattern recognition

UR - http://www.scopus.com/inward/record.url?scp=85012591507&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012591507&partnerID=8YFLogxK

U2 - 10.1049/el:19800611

DO - 10.1049/el:19800611

M3 - Article

AN - SCOPUS:85012591507

SN - 0013-5194

VL - 16

SP - 860

JO - Electronics Letters

JF - Electronics Letters

IS - 22

ER -

Comment: Algorithms for computing relative neighbourhood graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this