Maximizar la distancia mínima entre los puntos situados en un polígono

Question

Me gustaría maximizar el espacio mínimo entre un número fijo de puntos ( $x_i \in \mathbb{R}^2$ ) colocado dentro de un polígono en el plano. La separación mínima incluye la distancia al polígono.

Por lo tanto, estoy tratando de resolver $$ \max_{x_i,R} R \\ s.t. \quad ||x_i -x_j||_2 \geq R, \quad \forall\ i \neq j \\ a_k^Tx_i + R||a_k||_2 \leq b_k, \quad \forall\: i,k\\ Ax_i \leq b, \quad \forall \: i $$

Sin embargo, el primer conjunto de restricciones no es convexo. ¿Existe alguna relajación o aproximación conocida para este problema?

Answer 1

Se trata de una variante bastante compleja del problema de empaquetamiento de círculos (basta con buscar en Google): en ese caso se da $n$ círculos del mismo radio $R$ y se quiere determinar el máximo $R$ y su posición central para que no se superpongan y queden en un cuadrado unitario.

Es un problema no convexo bastante difícil. El tuyo parece aún más difícil. Hay algunas relajaciones convexas, pero normalmente son bastante flojas. Por ejemplo, usted podría mirar a una serie de documentos de KM Anstreicher sobre relajaciones SDP.