Packing circles into perimeter-minimizing convex hulls

We present and solve a new computational geometry optimization problem in which a set of circles with given radii is to be arranged in unspecified area such that the length of the boundary, i.e., the perimeter, of the convex hull enclosing the non-overlapping circles is minimized. The convex hull boundary is established by line segments and circular arcs. To tackle the problem, we derive a non-convex mixed-integer non-linear programming formulation for this circle arrangement or packing problem. Moreover, we present some theoretical insights presenting a relaxed objective function for circles with equal radius leading to the same circle arrangement as for the original objective function. If we minimize only the sum of lengths of the line segments, for selected cases of up to 10 circles we obtain gaps smaller than $$10^{-4}$$ 10 - 4 using BARON or LINDO embedded in GAMS, while for up to 75 circles we are able to approximate the optimal solution with a gap of at most $$14\%$$ 14 % .