I would like to maximize the minimum spacing between a fixed number of points ($x_i \in \mathbb{R}^2$) placed inside a polygon in the plane. The minimum spacing includes distance to the polygon.
Thus, I am trying to solve
$$
\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
$$
However, the first set of constraints are not convex.
Is there any known relaxation or approximation for this problem?
Best Answer
This is a fairly complex variant of the circle packing problem (just google it): in that case you are given $n$ circles of the same radius $R$ and you want to determine the maximal $R$ and their center position so that they do not overlap and stay in a unitary square.
Is is a non convex quite hard problem. Yours sounds even harder. There are some convex relaxations but usually quite loose. For instance you might look to a series of paper from KM Anstreicher about SDP relaxations.