The following geometrical proximity concepts are discussed: relative
closeness and geographic closeness. Consider a set V =
{v_{1},v_{2},...,v_{n}} of distinct points in a two-dimensional
space. The point v_{j} is said to be a relative neighbour of
v_{i} if

d_{p}(v_{i},v_{j}) ≤ max{d_{p}(v_{j},v_{k}), d_{p}(v_{j},v_{k})} for all v_{k} ∈ V,

where d_{p} denotes the distance in the L_{p} metric, 1
≤ p ≤ ∞. After dividing the space around the point v_{i}
into eight sectors (regions) of equal size, a closest point to v_{i}
in some region is called an octant (region, or
geographic) neighbour of v_{i}. For any L_{p} metric, a
relative neighbour of v_{i} is always an octant neighbour in some
region at v_{i}. This gives a direct method for computing all relative
neighbours, i.e. for establishing the relative neighbourhood
graph of V. For every point v_{i} of V, first search for the
octant neighbours of v_{i} in each region, and then for each octant
neighbour v_{j} found check whether the point v_{j} is also a relative
neighbour of v_{i}. In the L_{p} metric, 1 < p < ∞, the total
number of octant neighbours is shown to be Θ(n) for any set of
n points; hence, even a straightforward implementation of the above
method runs in Θ(n^{2}) time. In the L_{1} and L_{∞}
metrics the method can be refined to a Θ(n log n + m)
algorithm, where m is the number of relative neighbours in the
output, n − 1 ≤ m ≤ n (n − 1). The L_{1} (L_{∞})
algorithm is optimal within a constant factor.

@article{Kat1988J,
author = {Jyrki Katajainen},
title = {The region approach for computing relative neighbourhood graphs in
the $L_p$ metric},
journaltitle = {Computing},
volume = {40},
number = {2},
year = {1988},
pages = {147--161},
}