Constructing the relative neighborhood graph in 3-dimensional Euclidean space

Jerzy W. Jaromczyk, Mirosław Kowaluk

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


The relative neighborhood graph for a finite set S={p1,...,pN} of points, briefly RNG(S), is defined by the following formation rule: pipj is an edge in RNG(S) if and only if for all pkε{lunate}S-{pi, pj}, dist(pi, pj)≤max(dist(pi,pk), dist(pj,pk)). We show that RNG for point sets in R3 can be constructed in optimal space and O(N2log N) time. Also, combinatorial estimates on the size of RNG in R3 are given.

Original languageEnglish
Pages (from-to)181-191
Number of pages11
JournalDiscrete Applied Mathematics
Issue number2
StatePublished - Apr 15 1991

Bibliographical note

Funding Information:
* The work on this paper has been partially supported by the Research Committee Grant of the University of Kentucky and a grant from the Center for Robotics and Manufacturing Systems, University of Kentucky.

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Constructing the relative neighborhood graph in 3-dimensional Euclidean space'. Together they form a unique fingerprint.

Cite this