Cube Point Picking

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Let two points be picked randomly from a unit $n$-D Hypercube. The expected distance between the points $\Delta(N)$ is then

$$\Delta(1) = {\textstyle{1\over 3}}$$

$$\Delta(2) = {\textstyle{1\over 15}} [\sqrt{2}+2+5\ln(1+\sqrt{2}\,)]=0.521405433\ldots$$

$$\Delta(3) = {\textstyle{1\over 105}} [4+17\sqrt{2}-6\sqrt{3}+21\ln(1+\sqrt{2}\,)+42\ln(2+\sqrt{3}\,)-7\pi]$$

$$= 0.661707182\ldots$$

$$\Delta(4) = 0.77766\ldots$$

$$\Delta(5) = 0.87852\ldots$$

$$\Delta(6) = 0.96895\ldots$$

$$\Delta(7) = 1.05159\ldots$$

$$\Delta(8) = 1.12817\ldots.$$

The function $\Delta(n)$ satisfies

$${\textstyle{1\over 3}}n^{1/2}\leq \Delta(n)\leq ({\textstyle... ...1\over 3}\left[{1+2\left({1-{3\over 5n}}\right)^{1/2}}\right]}$$ (1)

(Anderssen et al. 1976).

Pick $N$ points $p_1$, ..., $p_N$ randomly in a unit $n$-cube. Let $C$ be the Convex Hull, so

$$C\equiv \left\{{\,\sum_{j=1}^N \lambda_jp_j : \lambda_j\geq ... ...for\ all\ } j {\rm\ and\ } \sum_{j=1}^N \lambda_j=1 }\right\}.$$ (2)

Let $V(n,N)$ be the expected $n$-D Volume (the Content) of $C$, $S(n,N)$ be the expected $(n-1)$-D Surface Area of $C$, and $P(n,N)$ the expected number of Vertices on the Polygonal boundary of $C$. Then

$$\lim_{N\to\infty} {N[1-V(2,N)]\over\ln N}={8\over 3}$$ (3)

$$\lim_{N\to\infty} \sqrt{N}[4-S(2,N)] = \sqrt{2\pi} \left[{2-\int_0^1 (\sqrt{1+t^2}-1)t^{-3/2}\,dt}\right]= 4.2472965\ldots,$$ (4)

and

$$\lim_{N\to\infty} P(2,N)-{\textstyle{8\over 3}}\ln N={\textstyle{8\over 3}}(\gamma-\ln 2) = -0.309150708\ldots$$ (5)

(Rényi and Sulanke 1963, 1964). The average Distance between two points chosen at random inside a unit cube is

$${\textstyle{1\over 105}}[4+17\sqrt{2}-6\sqrt{3}+21\ln(1+\sqrt{2}\,)+42\ln(2+\sqrt{3}\,)-7\pi]$$ (6)

(Robbins 1978, Le Lionnais 1983).

Pick $n$ points on a Cube, and space them as far apart as possible. The best value known for the minimum straight Line distance between any two points is given in the following table.

$n$	$d(n)$
5	1.1180339887498
6	1.0606601482100
7	1
8	1
9	0.86602540378463
10	0.74999998333331
11	0.70961617562351
12	0.70710678118660
13	0.70710678118660
14	0.70710678118660
15	0.625

See also Cube Triangle Picking, Discrepancy Theorem, Point Picking

References

Anderssen, R. S.; Brent, R. P.; Daley, D. J.; and Moran, A. P. ``Concerning $\int_0^1\cdots\int_0^1 \sqrt{{x_1}^2 +\ldots+{x_k}^2}\,dx_1\cdots dx_k$ and a Taylor Series Method.'' SIAM J. Appl. Math. 30, 22-30, 1976.

Bolis, T. S. Solution to Problem E2629. ``Average Distance Between Two Points in a Box.'' Amer. Math. Monthly 85, 277-278, 1978.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/geom/geom.html

Ghosh, B. ``Random Distances within a Rectangle and Between Two Rectangles.'' Bull. Calcutta Math. Soc. 43, 17-24, 1951.

Holshouser, A. L.; King, L. R.; and Klein, B. G. Solution to Problem E3217, ``Minimum Average Distance Between Points in a Rectangle.'' Amer. Math. Monthly 96, 64-65, 1989.

Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 30, 1983.

Rényi, A. and Sulanke, R. ``Über die konvexe Hülle von $n$ zufällig gewählten Punkten, I.'' Z. Wahrscheinlichkeits 2, 75-84, 1963.

Rényi, A. and Sulanke, R. ``Über die konvexe Hülle von $n$ zufällig gewählten Punkten, II.'' Z. Wahrscheinlichkeits 3, 138-147, 1964.

Robbins, D. ``Average Distance Between Two Points in a Box.'' Amer. Math. Monthly 85, 278, 1978.

Santaló, L. A. Integral Geometry and Geometric Probability. Reading, MA: Addison-Wesley, 1976.