# Relative neighborhood graphs in three dimensions

Published

Conference Paper

The relative neighborhood graph (RNG) of a set S of n points in M.d is a graph (S, E), where (p, q) ∈ E if and only if there is no point z G S such that max{d(p, z), d(q, z)} < d(p, q). We show that in ℝ3, RNG(S) has O(n4/3) edges. We present a randomized algorithm that constructs RNG(S) in expected time O(n3/2+∈) assuming that the points of S are in general position. If the points of S are arbitrary, the expected running time is P(n7/4+∈). These algorithms can be made deterministic without affecting their asymptotic running time.

### Duke Authors

### Cited Authors

- Agarwal, PK; Matoušek, J

### Published Date

- September 1, 1992

### Published In

- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

### Volume / Issue

- Part F129721 /

### Start / End Page

- 58 - 65

### International Standard Book Number 10 (ISBN-10)

- 089791466X

### Citation Source

- Scopus