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.
|Published - 1980
ASJC Scopus subject areas
- Electrical and Electronic Engineering