0
$\begingroup$

If I have $n$ points on the surface of a torus, and want to check the Euclidean length of all "three-hop paths" between two (newly added) fixed points $s,t$ at distance $||s-t||$ apart, I need to check the sum of the edge lengths over $ 2 {n \choose 2}$ paths.

With $n=3$ there are 6 paths I can form. With $n=4$, there are 12.

Using Boole, I can determine if any of these path lengths are shorter than some critical value, e.g. for $(x,y)$ and $(X,Y)$ two points in the plane....

Boole[Sqrt[X^2 + Y^2] + Sqrt[(X - x)^2 + (Y - y)^2] + 
   Sqrt[(d - x)^2 + y^2] < L]

returns 1 whenever the three-hop path is shorter than a length $L$, with $||s-t||=d$, and zero otherwise.

With three points, as mentioned, there are six routes. I would need six instances of Boole like the one above, each in 4 variables, in order to check all the paths to see if any were shorter than $L$.

I could then integrate these functions over all configurations of 3 points, to see what proportion of all configurations have a path of length less than $L$, for example.

Is there a way to write a function which takes in $n$, a natural number, and returns the Boole as above for me, with each of the lengths used in inclusive OR? So the above equation would be returned when $n=2$. With $n=3$, it would have $6$ separate conditions, any one of which returning true gives this Boole function the value 1, and is otherwise zero.

$\endgroup$
  • $\begingroup$ See also mathematica.stackexchange.com/questions/164590/… $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 15:53
  • $\begingroup$ Yes, also the paths a three “hops” long $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 20:09
  • $\begingroup$ I need to set up a numerical integral which gives the CDF of the length of the shortest path s —> t via two other nodes $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 20:10
  • 1
    $\begingroup$ So, if I understand correctly, given $n$ points, you'd like a function fun[s, t, L] that would return the proportion of 3-hop paths that are shorter than $L$ among all 3-hop paths. Then, you would integrate fun over s and t. This brute-force approach might be time-consuming... $\endgroup$ – anderstood Jan 31 '18 at 20:23
  • $\begingroup$ Yes. But is it possible to do? If it worked only for small n that would be fine $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 20:25
1
$\begingroup$

The following function ratio takes two points s and t, the list of $n$ points pts, and it returns the ratio of lengths shorter than length. It runs in 2ms for n=50 which is reasonable.

n = 50;
length = 4;
pts = RandomReal[{-1, 1}, {n, 2}];
s = {-1, 1}; t = -s;

ratio[s_, t_, l_] := Block[{},
  paths = {s}~Join~#~Join~{t} & /@ Subsets[pts, {2}];
  lengths = Total[Norm /@ Differences[#]] & /@ paths;
  1 - .5*Total[Sign[lengths - l] + 1]/Length@lengths]

To be used as ratio[s,t,length].

For example you can plot ratio for t at the origin and s integrated along the $x$ axis:

Plot[ratio[{x, 0}, {0, 0}, length], {x, -1, 1}]

enter image description here

Regarding your comment You want a function to return 1 if the shortest of all three-hop paths is shorter than $l$. Given that $n$ is finite, you could simply use If[ratio[s,t,l]==0, 1, 0]. The following function should also work (I did not test it):

shortQ[s_, t_, l_] := Block[{},
  paths = {s}~Join~#~Join~{t} & /@ Subsets[pts, {2}];
  lengths = Total[Norm /@ Differences[#]] & /@ paths;
  If[Min[lengths] <= l, 1, 0]]
$\endgroup$
  • $\begingroup$ So it looks at all paths of three hops from s to t, and gives the proportion of them less than l in Euclidean length. $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 21:03
  • $\begingroup$ Correct. Isn't that what you are looking for? $\endgroup$ – anderstood Jan 31 '18 at 21:05
  • $\begingroup$ Yes indeed. What I would like to do is numerically integrate this over general $d$-dimensional point configurations, so over an $nd$-dimensional integral. This should give the CDF of the path count less than l in length. $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 21:08
  • $\begingroup$ This works nicely. Thank you for such a quick response. $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 21:09
  • $\begingroup$ Can this potentially be modified to give a true/false output (0/1) whenever the shortest of all the three-hop paths (the "geodesic" path) is less than L? $\endgroup$ – Alexander Kartun-Giles Jan 31 '18 at 21:32

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.