Find the largest minimum distance of n points in a convex compact set

65 Views Asked by At

Suppose you have to place n points in a convex compact set X $\in R^m$, using the Euclidean distance as the metric, how does the largest minimum distance between those n points change with the number of points n?

To clarify, when you place n points in the set X, you can compute the minimum distance between those n points. I would like to have the placement such that this minimum distance is maximized. I assume that this largest minimum distance decreases with the number of points n. My question is at what rate this distance decreases?

2

There are 2 best solutions below

0
On

Since every nonempty compact convex subset of $R^m$ is homeomorphic to the closed unit ball of suitable dimension, your argument can be extended to the mth-dimensional inscribed regular polytope that connects the n points that you want to place in the convex set.

3
On

It would be difficult for a given $X$ and a given $k$ to find

$$\rho_{X,k}\colon =\max_{a_1, \ldots, a_k \in X} \min_{i\ne j} d(a_i, a_j)$$

except some easy particular cases ($X$ is a segment, or a circle).

I think that $\rho_{X, k}$ behaves like the radius of $k$ balls tightly packed inside $X$, so it should be

$$k \cdot \rho_{X,k}^n\simeq \operatorname{vol}(X)$$