4
$\begingroup$

If we have a unit hypersphere, with "approximately" evenly spaced points$^1$, is there any good upper bound on the minimum angle between nearby points?

On a unit circle, for $N$ equally spaced points, the minimum angle would be $2\pi/N$.

For a unit sphere, we can use the area of a spherical cap to get us a upper bound of the angle:

$$ A = \frac{4\pi}{N} = 2\pi \left(1-\cos(\theta)\right) \\ \theta = \cos^{-1}\left(1 - \frac{2}{N}\right) $$

Where $\theta$ here should be half of the angle between two neighboring points. This is an upper bound because it assumes we are completely covering the surface with circles around each point, which we can't do. The actual circles around each point would have to be smaller, so our angle would be smaller.

But what about for a higher dimensional hypersphere?

Addendum:

As Ross noted, the sphere packing density comes into play in this problem, which will likely make it intractable in higher dimensions...

I looked up the sphere packing densities (in Euclidean space, which is probably fine for large enough $N$) at Mathworld. The first 8 dimensions are the only ones that are listed (and I believe known), and they fall off fairly quickly with dimension (it looks close to linear for the first 8, but it is likely exponential or similar), in 8 dimensions the packing density is roughly .25.

An idea -- though it depends on getting a decent approximation for the sphere packing density in higher dimensions -- would be to use the sphere packing density to correct the area. In 3 dimensions:

$$ A = \delta_2 \frac{4\pi}{N} = \dots\\ \theta = \cos^{-1}\left(1-\delta_2 \frac{2}{N}\right) $$

where $\delta_2$ is the sphere packing density for 2 dimensions.

More: These lecture notes give an lower bound of the packing density of $2n\cdot2^{-n}$, and an upper bound of $2^{-0.599n}$, which have a pretty wide gap, but are enough to bound the problem at least.

$^1$ I realize that it isn't really trivial to find such a spacing of points on a hypersphere, but an approximation is fine.

$\endgroup$
1
$\begingroup$

For large $N$ there is a good approximation. The $n$ dimensional unit hypersphere has a surface of $$S_n(1)=\frac {2\pi^{\frac{n+1}2}}{\Gamma(\frac{n+1}2)}$$ The area of your spherical cap can be written as $\pi \theta^2$ if we take the first surviving term of the Taylor series for $\cos \theta$, which is the volume of a $2-$ball of radius $\theta$. Similarly the cap around a point has a surface which is approximately the volume of an $n-1$ ball of radius $\theta$, which is $$V_{n-1}(\theta)=\frac {\pi^{\frac {n-1}2}}{\Gamma(\frac {n+1}2)}\theta^{n-1}$$ We want $N$ of these volumes to add up to the available surface, so we have $$NV_{n-1}(\theta)=S_n(1)\\ N\frac {\pi^{\frac {n-1}2}}{\Gamma(\frac {n+1}2)}\theta^{n-1}=\frac {2\pi^{\frac{n+1}2}}{\Gamma(\frac{n+1}2)}\\N\theta^{n-1}=2\pi\\\theta=\left(\frac {2\pi}N\right)^{\frac 1{n-1}}$$ valid for large $N$ so the approximation of the cap by a flat ball is accurate. In your $2D$ case we would approximate the spherical cap by a flat circle. This also uses your approximation that we can cover the entire surface of the $n-$sphere with our caps. I don't have any idea how the packing density varies with dimension.

$\endgroup$
2
  • $\begingroup$ see the addition to my question. $\endgroup$ – Andrew Spott Aug 29 '18 at 14:41
  • $\begingroup$ I agree with your idea. It inserts a factor $\delta_{n-1}$ inside the parentheses on the right. $\endgroup$ – Ross Millikan Aug 29 '18 at 14:45

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.