Abstract
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 language | English |
---|---|
Pages (from-to) | 181-191 |
Number of pages | 11 |
Journal | Discrete Applied Mathematics |
Volume | 31 |
Issue number | 2 |
DOIs | |
State | Published - 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