# Relative Neighbourhood Graph

Is there some way to efficiently compute the relative neighbourhood graph on $$n$$ Euclidean points in $$\mathbb{R}^{d}$$?

Though one can simply define

MaxDist[x_, y_, point_] := Max[{EuclideanDistance[x, y],
EuclideanDistance[x, point],
EuclideanDistance[point, y]}]


and then use it on every $${n \choose 3}$$ triples of points to determine if, among all possible alternatives, the link is shortest, perhaps a nicer method is available using a matrix of Euclidean distances?

• "a matrix of Euclidean distances" - that is what DistanceMatrix[] is for. – J. M. is in limbo Oct 8 '18 at 16:27
• Yes, but how do you compare all triples effectively? You have to do this for multiple tripes for each $n$ points. Perhaps Nearest, finding local points to a region, and then testing on those triples for each pair? – Alexander Kartun-Giles Oct 8 '18 at 16:29
• Yes, I see what you mean; it will quickly be combinatorically prohibitive. Nearest[] with a radial restriction might be workable, tho. – J. M. is in limbo Oct 8 '18 at 16:32
• The Wikipedia entry gives the definition specifically for $\mathbb{R}^2$. Is this something that people use also in $\mathbb{R}^d, d \ge 3$? – Szabolcs Oct 11 '18 at 12:24

## 2 Answers

IGraph/M now has functions for computing a few types of proximity graphs, including the relative neighbourhood graph and β-skeletons.

IGRelativeNeighborhoodGraph@RandomPoint[Disk[], 1000]


This is still a work-in-progress and performance optimizations, as well as generalizations, are possible in the future.

# Ad-hoc implementation of Relative Neighborhood Graph (RNG)

Under the heuristic assumption that that each vertex in a RelativeNeighborhoodGraph will have at most valence 6, this could be a way to exploit Nearest to compute it:

ClearAll[RelativeNeighborhoodGraph];
RelativeNeighborhoodGraph[pts_?((MatrixQ[#] && Dimensions[#][[2]] == 2) &)] :=
Module[{nf, i, j, p, q, edgelengths, edges},
nf = Nearest[pts -> Automatic];
i = Join @@ Rest[Transpose[nf[pts, {7, ∞}]]];
j = Join @@ ConstantArray[Range[Length[pts]], 6];
edges = DeleteDuplicates[Sort /@ Transpose[{i, j}]];

{i, j} = Transpose[edges];
p = pts[[i]];
q = pts[[j]];
edgelengths = Sqrt[Dot[Subtract[p, q]^2, ConstantArray[1., 2]]];
edges = Pick[
edges,
MapThread[
{x, y, d} \[Function] Length[Intersection[nf[x, {∞, d}], nf[y, {∞, d}]]],
{p, q, edgelengths + 100 $MachineEpsilon} ], 2 ]; Graph[Range[Length[pts]], UndirectedEdge @@@ edges, VertexCoordinates -> pts] ]  Usage example: SeedRandom[20181008]; pts = RandomReal[{-1, 1}, {1000, 2}] RelativeNeighborhoodGraph[pts]  # Implementation of $$\beta$$-Skeleton for $$\beta \geq 1$$ The $$2$$-Skeleton is precisely the RNG. So we can try to compute this one. The strategy is the same as above: First sieving out a list of edges that a as-small-as-possible superset of the $$\beta$$-Skeleton's edge list. For $$\beta \geq 1$$, we may exploit that the $$\beta$$-Skeleton is a subgraph of the edge-graph of the Delaunay triangulation. So we may skip the heuristic sieving argument from above and start from the edges of DelaunayMesh[pts]. ClearAll[BetaSkeleton]; BetaSkeleton[ pts_?((MatrixQ[#] && Dimensions[#][[2]] == 2) &), β_ /; β >= 1 ] := Module[{nf, i, j, p, q, r, edgelengths, edges}, nf = Nearest[pts -> Automatic]; edges = MeshCells[DelaunayMesh[pts], 1, "Multicells" -> True][[1, 1]]; {i, j} = Transpose[edges]; p = pts[[i]]; q = pts[[j]]; r = 0.5 β; edgelengths = Sqrt[Dot[Subtract[p, q]^2, ConstantArray[1., 2]]]; edges = Pick[edges, MapThread[ {x, y, d} \[Function] Length[ Intersection[ nf[x + (r - 1) (x - y), {∞, d}], nf[y + (r - 1) (y - x), {∞, d}] ] ], {p, q, r (edgelengths + 100$MachineEpsilon)}
],
2
];
Graph[Range[Length[pts]], UndirectedEdge @@@ edges, VertexCoordinates -> pts]
]


Examples:

BetaSkeleton[pts, 2.0]


BetaSkeleton[pts, 2.5]


• I was working on something like R=RegionIntersection[Disk[{-0.5, 0}, 1], Disk[{0.5, 0}, 1]] and RegionMember[R, #] & /@ pts, since the relative neighbourhood graph is simply the beta skeleton with $\beta=2$, hence the empty lune approach might work, but this is much faster. – Alexander Kartun-Giles Oct 8 '18 at 17:15
• Is there some way to calculate the beta skeleton, of which the RNG is the special case? – Alexander Kartun-Giles Oct 8 '18 at 18:03
• You want the lune-based beta skeletton, right? – Henrik Schumacher Oct 8 '18 at 18:34
• Yes exactly, it is a very nice thing to have given all the special cases it can produce. – Alexander Kartun-Giles Oct 8 '18 at 18:44
• Thank you for this valuable addition. – Alexander Kartun-Giles Oct 9 '18 at 12:03