8
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ "a matrix of Euclidean distances" - that is what DistanceMatrix[] is for. $\endgroup$ Oct 8, 2018 at 16:27
  • 1
    $\begingroup$ 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? $\endgroup$
    – apkg
    Oct 8, 2018 at 16:29
  • 3
    $\begingroup$ Yes, I see what you mean; it will quickly be combinatorically prohibitive. Nearest[] with a radial restriction might be workable, tho. $\endgroup$ Oct 8, 2018 at 16:32
  • $\begingroup$ 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$? $\endgroup$
    – Szabolcs
    Oct 11, 2018 at 12:24

2 Answers 2

3
$\begingroup$

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

IGRelativeNeighborhoodGraph@RandomPoint[Disk[], 1000]

enter image description here

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

$\endgroup$
8
$\begingroup$

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]

enter image description here

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]

enter image description here

BetaSkeleton[pts, 2.5]

enter image description here

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – apkg
    Oct 8, 2018 at 17:15
  • $\begingroup$ Is there some way to calculate the beta skeleton, of which the RNG is the special case? $\endgroup$
    – apkg
    Oct 8, 2018 at 18:03
  • 1
    $\begingroup$ You want the lune-based beta skeletton, right? $\endgroup$ Oct 8, 2018 at 18:34
  • $\begingroup$ Yes exactly, it is a very nice thing to have given all the special cases it can produce. $\endgroup$
    – apkg
    Oct 8, 2018 at 18:44
  • $\begingroup$ Thank you for this valuable addition. $\endgroup$
    – apkg
    Oct 9, 2018 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.