4
$\begingroup$

Say I have to place N points in $\mathbf{R}^2$ inside a circle of radius $R$.

I want to position them so as to maximize the sum of nearest distances i.e. solve the following problem \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} where $s$ is a constant larger than $2$

My aim is to characterize the behavior of this optimal value as the number of points $n$ becomes large. So even asymptotic order analysis will be helpful.

If it makes things easier, consider other constraint sets (eg. A square of side length $A$)

$\endgroup$
  • 2
    $\begingroup$ Related: math.ucsd.edu/~ronspubs/98_01_circles.pdf $\endgroup$ – vadim123 Oct 10 '14 at 3:00
  • $\begingroup$ If the question becomes minimize sum of distance inverse (repulsive coulomb potential) in $R^3$, it becomes how chemists predict the shape of molecules (VSEPR model). I've never seen rigorous math derivation of the cases of large $n$ in similar problems. I'm curious about this too. $\endgroup$ – user175968 Oct 13 '14 at 5:02
1
+50
$\begingroup$

Not an exact solution, but an approximation (that may or not not be good enough):

Assumption 1: Solving the problem for the infinite plane provides a solution that is a reasonable approximation for the circle problem.

Assumption 2: The solution is somewhat uniform; for all points $x$, the distance to its nearest neighbor is $\delta$.

This corresponds to the problem of packing $n$ circles with radius $\frac{1}{2}\delta$ and center $x_i$. The densest solution is placing the $x_i$ on the vertices of a triangular tiling with equilateral triangles.

One way to construct this tiling inside a circle is to chose $\delta$ such that $\delta$ divides $r$ and to place the first vertex $x_0$ in the center of the circle. Add two more vertices to create the first triangle (with arbitrary orientation), then add the remaining triangles and discard all vertices that are not on/in the circle. This creates a neat, symmetric result, but has the disadvantage that $n$ results from $r$ and $\delta$, and cannot be given.

This solution is not optimal (look at the vertices closest to the circle perimeter), but for large $n$ it should approach the optimum.

$\endgroup$
1
$\begingroup$

You can use Lloyd's relaxation:

  1. Place the points randomly inside the circle.
  2. Iterate until convergence:
    a) Compute the clipped Voronoi diagram of the points and the circle
    b) Move each point to the center of mass of its Voronoi cell

Comments:

In 2a), the clipped Voronoi diagram is the intersection of the circle and the "ordinary" Voronoi diagram of the points. However, the available methods that compute it, usually assume $L_2$ norm (you mentioned $s > 2$, so be careful).

In 2b), compute the center of mass with respect to the distance you are using (whatever $s$ you have).

This approach has the advantage that you only specify the number of points $n$. In the related circle packing and Poisson disk sampling problems, you provide the circle radius or the desired minimal inter-point distance.

Reference:

Here is a link to a paper for computing the clipped Voronoi diagram (there are planty more on Google).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.