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 language | English (US) |
|---|---|
| Journal | Electronics Letters |
| Volume | 16 |
| Issue number | 22 |
| State | Published - 1980 |
ASJC Scopus subject areas
- Electrical and Electronic Engineering