Let $S\_n$ be a set of $n$ points belonging to $\mathcal{B}\_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|\_2\le 1\}$, where $d\ll \log(n)$.
Let $s\_n$ and $\ell\_n$ be respectively defined as follows:


$$s\_n:={n\choose 3}^{-1}\cdot\!\!\!\!\sum\_{1\le i<j<k\le n}\min\left(\|\mathbf{x}\_i-\mathbf{x}\_j\|\_2, \|\mathbf{x}\_j-\mathbf{x}\_k\|\_2, \|\mathbf{x}\_k-\mathbf{x}\_i\|\_2\right)~,$$


$$\ell\_n:={n\choose 3}^{-1}\cdot\!\!\!\!\sum\_{1\le i<j<k\le n}\max\left(\|\mathbf{x}\_i-\mathbf{x}\_j\|\_2, \|\mathbf{x}\_j-\mathbf{x}\_k\|\_2, \|\mathbf{x}\_k-\mathbf{x}\_i\|\_2\right)~.$$




---


**Question:** How can we find a (*tight if possible*) lower and upper bound for the ratio $\rho\_n=\frac{\ell\_n}{s\_n}$?



Euclidean distance bound with geometric constraints
**For the upper bound:**


Take $n/2$ points arbitrarily close to $0$ and $n/2$ points arbitrarily close to 1.


Then, in $3/4$ths of the triangles, there will be a point close to $0$ and a point close to $1$, and therefore the longest edge will be close to 1. Otherwise, all 3 vertices will be at 0 (or at 1) and the longest edge is 0. Thus, $l\_n \approx 3/4$.


Furthermore, in any triangle, there will be two points close to $0$ or two points close to $1$, and therefore the smallest edge will be close to $0$. Thus, $s\_n \approx 0$.


Consequently, $l\_n/s\_n \approx \infty$.


$\\ $


**For the lower bound:**


Evenly divide the $n$ points among the $d$ unit vectors, $e\_1,\ldots,e\_d$. The distance between any two unit vectors is $\sqrt{2}$. Approximately $\left(1-\frac{1}{d^2}\right)$ of the triangles contain at least two different $e\_i$'s, so $l\_n \approx \sqrt{2} \left(1-\frac{1}{d^2}\right)$.


Approximately $\left(1-\frac{1}{d}\right)\left(1 - \frac{2}{d}\right)$ of the triangles contain three different $e\_i$'s, and so $s\_n \approx \sqrt{2}\left(1-\frac{1}{d}\right)\left(1 - \frac{2}{d}\right)$. Taking the ratio, $l\_n/s\_n \approx \frac{d+1}{d-2}$. This ratio heads to $1$ as $d \rightarrow \infty$.


$\\ $


PS. This can be tightened a little by noting that in the $d$-dimensional sphere, you can actually take $d+1$ equidistant points, and therefore $l\_n/s\_n \approx \frac{d+2}{d-1}$.


PPS. As an example, suppose that $d=20$ and $n=200$. Then, we put $200/20=10$ points at each of $e\_1,\ldots,e\_{20}$. Draw the first vertex at random. Draw two more vertices at random. The odds that they are at the same $e\_i$ is $\approx 1/d^2=1/400$. Therefore, approximately $399/400$ of triangles will have vertices at at least two different $e\_i$, and so $l\_n \approx \sqrt{2} (399/400)$. When we draw three vertices at random, the odds that they are all different $e\_i$ is $19/20 \cdot 18/20$ (because the second draw has to avoid the first and the third draw has to avoid the first two). Therefore, $s\_n \approx \sqrt{2} (342/400)$ and $l\_n / s\_n \approx 399/342 = 21/18 = 7/6 = 1.1\overline{6}$. The approximations come in when we estimate the probability that a randomly drawn triangle has vertices at different $e\_i$'s because once a single vertex is draw at $e\_i$, there are now less vertices available there, and so the odds of repetition are slightly smaller.


