Approximate MAXMIN distance between K points in N dimension

less than 1 minute read

When I was reading paper, namely The Relationship Between High-Dimensional Geometry and Adversarial Examples which generates a lot of points on the shell in high dimension, I thought of an interesting problem: what is the maximum of their minimum mutual distance. I googled and found this and this, while the first link asked exactly what I meant but got no ideal solution and the second one only solved a special case. However, though it might be intuitively easy to think about how the MAXMIN case looks like, it is not straightforward to get a unified solution. That motivates this blog.

I chose \(N\) from \(2\) to \(100\) with step \(5\) and \(K\) from \(10\) to \(200\) with step \(20\) and ran simulation for all these cases in Google Colab (code) and got this:

result

The illustration provides an insight which is also intuitively true. The MAXMIN increases as \(N\) (dimension) increases and decreases as \(K\) (number of points) increases. In addition, \(N\) has larger effect than $K$, and both seem to have convergent effects.

This blog is rather crude, so feel free to make improvements to my simulation.

Total readers: