# Maximizing minimum distance between points placed in a polygon

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?

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.
• Ah, for some reason I thought the circle-packing problem was maximizing $n$ given fixed $R$ and that this would be somewhat different, but I guess not. Mar 22, 2014 at 18:43