Ubicación óptima de puntos dentro de un conjunto

Question

Decir que tengo para colocar puntos N en $\mathbf{R}^2$ dentro de un círculo de radio de $R$.

Quiero posición de ellos con el fin de maximizar la suma de distancias más cercano es decir, resolver el siguiente problema \begin{align} \max_{x_1, ... x_n} &\sum_{i = 1}^{n} \min_{j \neq i} |x_i - x_j|^s \\ \text{s.t. } |x_i| &< R \end{align} donde $s$ es una constante mayor que $2$

Mi objetivo es caracterizar el comportamiento de este valor óptimo como el número de puntos de $n$ se hace más grande. Así que incluso asintótica análisis de orden será de ayuda.

Si hace las cosas más fáciles, considere la posibilidad de otros conjuntos de restricciones (por ejemplo. Un cuadrado de lado de longitud $A$)

Answer 1

No exactamente una solución, pero una aproximación (que puede o no ser lo suficientemente bueno):

Hipótesis 1: Resolver el problema para el plano infinito ofrece una solución que es una aproximación razonable para el círculo problema.

Hipótesis 2: La solución es algo uniforme; para todos los puntos de $x$, la distancia a su vecino más cercano es $\delta$.

Esto se corresponde con el problema de embalaje $n$ círculos con un radio de $\frac{1}{2}\delta$ y el centro de la $x_i$. La más densa solución es la colocación de la $x_i$ en los vértices de un triangular de mosaico con triángulos equiláteros.

Una forma de construir este mosaico dentro de un círculo se eligió $\delta$ tal que $\delta$ divide $r$ y para colocar el primer vértice $x_0$ en el centro del círculo. Añadir dos más vértices para crear el primer triángulo (con arbitraria), luego añadir el resto de los triángulos y descartar todos los vértices que no están en el círculo. Esto crea un aseado, simétrica resultado, pero tiene la desventaja de que $n$ resultados de$r$$\delta$, y no se puede dar.

Esta solución no es óptima (mira los vértices más cercanos al círculo de perímetro), pero para un gran $n$ debe acercarse a la óptima.