# Maximum of all distances between any pairs of vertices of a random triangle

Given a set $$S_n$$ of $$n$$ points selected uniformly at random in a $$d$$-ball, I want to estimate the average length of the longest side of a triangle having as vertices any three distinct points of $$S_n$$, when $$n\gg d\gg 1$$. Below you can find my approach, which unfortunately does not scale well with the number of points $$n$$ nor the number of dimensions $$d$$. Is it possible to improve it to make it more scalable?

n:=300; d:=30;
p := RandomPoint[Sphere[d], {n}];
x:=EuclideanDistance @@@ Subsets[p, {3}][[1 ;; , 1 ;; 2]];
y:=EuclideanDistance @@@ Subsets[p, {3}][[1 ;; , 2 ;; 3]];
z:=EuclideanDistance @@@ Drop[Subsets[p, {3}], None, {2}];
Mean[Map[Max, Transpose[{x,y,z}]]]

• maybe n := 300; d := 30; p := RandomPoint[Sphere[d], {n/3, 3}]; xyz := Apply[EuclideanDistance, Subsets[#, {2}] & /@ p, {2}]; Mean[Map[Max, Transpose[xyz]]]? – kglr Nov 30 '20 at 22:00
• Thank you @kglr ! Why is your approach so fast compare to mine? I am new to Wolfram Language. What is the most significant difference? – Penelope Benenati Nov 30 '20 at 23:10
• Penelope, it is faster because it is not correct:) – kglr Nov 30 '20 at 23:11
• Yes,you need Ball[] – cvgmt Nov 30 '20 at 23:24
• since you defined p, x, y and z with SetDelayed, p is reevaluated every time it appears in x (similarly for y and z) . That is, a different p is used when you get x, y and z. – kglr Nov 30 '20 at 23:39

Maybe

SeedRandom
n = 300; d = 30;
p = RandomPoint[Sphere[d], {n, 3}];
xyz =  Apply[EuclideanDistance, Subsets[#, {2}] & /@ p, {2}];

Mean[Map[Max, xyz]]

1.5164


If we use Ball[d] instead of Sphere[d] we get 1.47179.

And a modification of your code (eliminating repeated invocations of Subsets[#,3] on p):

SeedRandom
n = 300; d = 30;
p = RandomPoint[Sphere[d], {n}];
xyz = With[{s3 = Subsets[p, {3}]},
Apply[EuclideanDistance, Subsets[#, {2}] & /@ s3, {2}]];
Mean[Map[Max, xyz]]

1.51594


If we replace Sphere[d] with Ball[d] we get 1.46985.

• Thank you a lot @kglr ! – Penelope Benenati Nov 30 '20 at 23:49
• @PenelopeBenenati, my pleasure. Thank you for the accept. – kglr Nov 30 '20 at 23:56

Seems no so effective.

Here we use RandomPoint to select uniform points in Ball[] and use RandomSample to select three points to construct a random triangle.

SeedRandom;
n = 300;
d = 30;
pts = RandomPoint[Ball[d], n];
Table[Max @@
EuclideanDistance @@@ Subsets [RandomSample[pts, 3], {2}], {i,
200000}] // Mean


1.46926

• Thank you very much @cvgmt ! This approach seems to be really fast! – Penelope Benenati Dec 1 '20 at 0:06
• @PenelopeBenenati Thanks your vote up！ – cvgmt Dec 1 '20 at 0:10
• You are welcome! Why did you replace RandomChoice by RandomSample? – Penelope Benenati Dec 1 '20 at 0:12
• @PenelopeBenenati since RandomSample select three distinguish points and RandomChoice cannot. Perhaps we also need to find a way to avoid co-line and select the real triangles. – cvgmt Dec 1 '20 at 0:15
• I see, thank you! – Penelope Benenati Dec 1 '20 at 0:16