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$
  • 1
    $\begingroup$ "a matrix of Euclidean distances" - that is what DistanceMatrix[] is for. $\endgroup$ – J. M. is in limbo Oct 8 '18 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$ – Alexander Kartun-Giles Oct 8 '18 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$ – J. M. is in limbo Oct 8 '18 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 '18 at 12:24
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$
  • $\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$ – Alexander Kartun-Giles Oct 8 '18 at 17:15
  • $\begingroup$ Is there some way to calculate the beta skeleton, of which the RNG is the special case? $\endgroup$ – Alexander Kartun-Giles Oct 8 '18 at 18:03
  • 1
    $\begingroup$ You want the lune-based beta skeletton, right? $\endgroup$ – Henrik Schumacher Oct 8 '18 at 18:34
  • $\begingroup$ Yes exactly, it is a very nice thing to have given all the special cases it can produce. $\endgroup$ – Alexander Kartun-Giles Oct 8 '18 at 18:44
  • $\begingroup$ Thank you for this valuable addition. $\endgroup$ – Alexander Kartun-Giles Oct 9 '18 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.