6
$\begingroup$

I have a set of circles of varying radii residing in 2D space. Some of these circles overlap. I would like to rearrange the circles such that a) they do not overlap; and b) the total distance that the circles have to move is minimized (this can be absolute distance or squared distance, I do not care at this point).

If none of the circles overlap in their initial positions, then the current position is optimal and the objective function is 0.

If there are exactly two circles that overlap, the problem is easy. I can draw a line that connects their two centers and move the circles along that line until they no longer overlap. But when three or more circles are involved, I'm not sure how to approach the problem.

See below for an example of initial positions, as I described I would like these circles to shift such that they don't overlap and total distance they have to move is minimized.

enter image description here

I found a similar question at Math SE here (and perhaps this question is better suited there), but it assumes some circles' positions are fixed (none of my circles are fixed) and the given answer seems to be a heuristic that relies on that property.

$\endgroup$

2 Answers 2

6
$\begingroup$

Assuming you want to avoid overlapping interiors (for example, concentric circles would not be allowed), you can solve the problem via (nonconvex) nonlinear programming as follows. Let $(\bar{x}_i,\bar{y}_i)$ be the given centers and $\bar{r}_i$ the given radii. The problem is to minimize $$\sum_i \sqrt{(x_i-\bar{x}_i)^2+(y_i-\bar{y}_i)^2}$$ subject to constraints $$(x_i-x_j)^2+(y_i-y_j)^2 \ge (\bar{r}_i+\bar{r}_j)^2 \quad \text{for $i<j$}$$ that prevent disks $i$ and $j$ from overlapping.

$\endgroup$
7
  • 1
    $\begingroup$ And don't forget to use a "rigorous" (e.g., branch and bound) global optimization solver, so that you don't end up with a non-globally optimal local minimum. If (sum of) squared distance moved is used in the objective function, a global non-convex QCQP solver could be used for this purpose. $\endgroup$ Commented May 16 at 19:01
  • $\begingroup$ Is GUROBI part of the rigorous global optimization solvers for MIQCP ? $\endgroup$
    – NormalFit
    Commented May 17 at 13:12
  • $\begingroup$ @NormalFit Yes. $\endgroup$ Commented May 17 at 18:27
  • $\begingroup$ @NormalFit There are no integer variables here. $\endgroup$
    – RobPratt
    Commented May 17 at 19:10
  • 1
    $\begingroup$ Branch and bound in global optimization for continuous variables is a way of finding or bounding the global optimum despite non-convexity.. $\endgroup$ Commented May 18 at 12:35
0
$\begingroup$

A constrained stress majorization formulation [1] of the same problem can guarantee monotone convergence:

\begin{array}{ll} \text{minimize} & \sum_{i} (||\mathbf{x_i} - \mathbf{x_\bar{i}} || - \epsilon)^2 \\ \text{subject to}& (x_i - x_j)^2 + (y_i - y_j)^2 \ge (r_i + r_j)^2 \\ \end{array}

Here $x_\bar{i}$ represents the original vector position of a circle, and $\epsilon$ controls how close to the initial position is close enough.

[1] https://www.vis.uni-stuttgart.de/documentcenter/staff/sedlmaml/papers/wang2017graph.pdf

$\endgroup$
1
  • $\begingroup$ The obj is a minor issue (just square it to get rid of the square root or add an epsilon as you did). The non-convexity of the non-overlap constraints is more of an issue if you want a proven global optimum. $\endgroup$ Commented May 20 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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