Packing circles into perimeter-minimizing convex hulls

Abstract

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}$ 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\%$.

1 Introduction

Observing the loading process of trucks led us to an interesting, but to our surprise, not studied problem neither in the Operations Research nor in the Computational Geometry community. In the logistics industry, circular items like drums or pipes are packed and secured with lashing straps. In order to save straps and the space usage of such circle shaped items on a truck’s loading area, the perimeter of the used lashing strap should be as small as possible. Given this real-world situation, we can transfer the observation into mathematical language and define the following novel arrangement problem: A finite set of 2-dimensional (2D) circular discs with given and, possibly, different radii has to be arranged such that the length of the boundary of the convex hull enclosing these circular discs is minimized. The circular discs are placed freely and they must not overlap each other. In the following, we use the terms circular discs and circles synonymously. In the mathematical literature the term circle is only used for the boundary or perimeter of the circular discs (e.g., see  [16]).

A general overview on arrangements, packing or covering of geometric objects can be found in [3, 4] or [6] . In [16], an algorithm with a running time of ${\mathcal {O}} (n\log n)$ derives the minimal convex hull of possibly overlapping circles which are fixed in a plane.  [1] studies different approximation algorithms to place two arbitrary convex sets in a plane such that the surrounding perimeter is minimized. Polygonal convex hulls are computed in [2]. The authors formulate the optimal clustering problem with a wide range of applicable problems including minimal containment of a pair given free translated and rotated shapes (bounded by circular arcs and line segments) in a rectangle, circle, convex polygon or convex hull, which supports applications in packing irregular objects, selecting or designing containers, and hole filling. The paper presents non-linear programs (NLP) and solution algorithms and provides new benchmark instances of finding the containing region that has either minimal area, perimeter or homothetic coefficient of a given container, as well as finding the convex polygonal hull (or its approximation) of a pair of objects. In contrast to [1] and [2], we consider the minimization of the perimeter of the convex hull of multiple circles of different size which can be moved freely in a certain sub-area of the 2D plane, e.g., a rectangle, but must not overlap each other. Thus, with the change of the position of circles, the shape and structure of the surrounding convex hull can also be changed.

Due to the possibility of changing the position of circles, the stated problem is closely related to the well-known circular packing problems (CPP), in which a given set of circles of arbitrary size have to be placed inside a container without overlapping each other. The container can either be rectangular or circular and the circles can arbitrarily be placed horizontally as well as vertically (cf. [5, 7, 17, 18] and [19]). Due to the importance for logistical problems, balancing conditions for circular packing problems are considered in the CPP. To answer the NP-hard decision problem whether the circles fit into the given container (see [8]), the circles are packed such that their total radii (if the container is circular) or the area of the required container (if the container is rectangular) is minimized. In this paper, we do not minimize the target domain, i.e., surrounding circle or rectangle, instead we minimize the perimeter of the convex hull enclosing the circular discs, or circles for short, fitting into the target domain. We thus do not pack circles in a given container of known shape, but rather arrange them in a sub-part of the 2D plane, and find their arrangement by minimizing the length of the perimeter of the convex hull. The convex hull, of course, has to fit within the given target domain. In the following, we will denote the problem as the minimal perimeter problem (MPP).

From a packing perspective, the length of the ribbon required to hold circular objects together should be as small as possible, e.g., in order to save material costs. However, the applications of the MPP are not restricted to the packing field. By solving the problem we can also find important answers for cutting problems. Given a block with a convex structure, the MPP provides an answer to the question of how many circles with given and arbitrary radii can be cut out. The assumption that the block is convex represents generalization of the circular cutting problem in which the circles are cut out from a circular block (see [9]).

Among the major contributions of this paper are:

• 1. novel mathematical programming models, i.e., closed mixed-integer non-linear programming (MINLP) models for the MPP;

• 2. proofs related to the structure of the boundary of the convex hull;

• 3. analytic solutions for smaller cases and special configurations;

• 4. polylithic¹ approaches for computing near optimal configurations for larger sets of circles for which the nonlinear and global solvers do not find feasible points in several hours.

The remainder of the paper is structured as follows: In Sect.  2 we derive the model formulation for the MPP. In Sect. 2.2 we describe the correspondence between minimal perimeter and area of the surrounding convex hull of packed circles. Analytic solutions are derived in Sect. 3. Numerical experiments are defined and presented in Sect. 4. Conclusions in Sect. 5 complete this paper.

2 Model formulation for the MPP

In this section we derive the mathematical model for the MPP. In Sect. 2.1, we present the required terminology and state the mathematical problem. The calculation of the convex hull of a set of circles is given in Sect. 2.3.

2.1 Problem definition

Within the paper we use column vectors in ${\mathbb {R}}^{2}$, e.g., $\mathbf{x}\in {\mathbb {R}}^{2}$. Vector $\mathbf{x}^{\mathrm {T}}$ is the transposed vector of $\mathbf{x}$ and is, thus, a row vector. The two dimensions of the plane are referenced by $d\in {\mathcal {D}}=\{{1,2\}}$, where 1 and 2 represents the first (x-axis) and second dimension (y-axis), respectively. Given two points $\mathbf{v}_{1}=(v_{11},v_{21})$ and $\mathbf{v}_{2}=(v_{12},v_{22})$ in the 2D plane, we calculate the distance between both points by means of the 2-norm with

$$\begin{aligned} \left\| \mathbf{v}_{1}-\mathbf{v}_{2}\right\| _{2}=\sqrt{\sum _{d\in {\mathcal {D}}}\left( v_{d1}-v_{d2}\right) ^{2}}\quad . \end{aligned}$$

A finite set ${\mathcal {I}}$ of n circles $i \in {\mathcal {I}}$, i.e. $| {\mathcal {I}}|=n$, with radii $R_{i}>0$ is to be placed in a 2D plane. The position of each circle $i\in {\mathcal {I}}$ is described by the coordinate vector $\mathbf{x}_{i}^{\mathrm {0}}$. The boundary or perimeter $\partial {\mathcal {S}}$ of the convex hull ${\mathcal {S}}$ hosting the circles consists of line segments and circular arcs of a subset ${\mathcal {I}}^{\mathrm {out} }\subseteq {\mathcal {I}}$ of arc-contributing circles; see Sect. . Circles contributing to the convex hull will be denoted by outer circles, while all other circles are inner circles. Note that circles in most cases contribute at most one arc, but in special cases they can contribute up to four arcs as displayed in Fig. 12.

Set ${\mathcal {J}}=\left\{ 1,\ldots ,N^{\mathrm {J}}\right\}$ contains directed line segments required to construct the boundary $\partial \mathcal { S}$ of the convex hull ${\mathcal {S}}$. If ${\mathcal {I}}^{\mathrm {out}}\ =\left\{ i_{1},\ldots ,i_{k}\right\} \subset {\mathcal {I}}$ is the subset of outer circles contributing an arc to $\partial {\mathcal {S}}$, then $n-k$ circles are either in the interior of ${\mathcal {S}}$ or just touch $\partial {\mathcal {S}}$. As $\partial {\mathcal {S}}$ has the homotopic type of a topological circumference, there have to be exactly $m<N^{\mathrm {J}}$ line segments ${j}\in {\mathcal {J}}$ if we have $m\ge 2$ outer circles contributing arcs to $\partial {\mathcal {S}}$. In the following indices i and j refer to the circles and line segments involved in the MPP.

Each line segment $j\in {\mathcal {J}}$ is defined by outgoing and ingoing vertices $\mathbf{v}_{j}^{\mathrm {\text {al}}}$ and $\mathbf{v}_{j}^{\mathrm { \text {la}}}$, respectively. The vertices $\mathbf{v}_{j}^{\mathrm {\text {al}} }$ and $\mathbf{v}_{j}^{\mathrm {\text {la}}}$ are points on two adjacent circles where the vertices $\mathbf{v}_{j-1}^{\mathrm {\text {la}}}$ and $\mathbf{v}_{j}^{\mathrm {\text {al}}}$ establish the tangential points one the same circle’s arc segment being part of $\partial {\mathcal {S}}$. An arc for circle i is therefore defined by the circle’s center, $\mathbf{x}_{i}^{ \mathrm {0}}$, as well as vertices $\mathbf{v}_{j-1}^{\mathrm {\text {la}}}$ and $\mathbf{v}_{j}^{\mathrm {\text {al}}}$ for $j=2,\ldots ,m-1$ and  $\mathbf{v}_{m}^{\mathrm {\text {la}}}$ and $\mathbf{v}_{1}^{\mathrm {\text {al}} }$. We define $\mathbf{v}_{0}^{\mathrm {\text {la}}}$ to be $\mathbf{v}_{m}^{ \mathrm {\text {la}}}$. The arc of the circle containing vertex $\mathbf{v} _{j}^{\mathrm {\text {al}}}$ is denoted by outgoing arc while the arc containing vertex $\mathbf{v}_{j}^{\mathrm {\text {la}}}$ is denoted by ingoing arc. Figure 1 shows the arrangement of four circles $i_{1}$ to $i_{4}$ with the two outgoing $\mathbf{v}_{1}^{\mathrm {al} }$ and $\mathbf{v}_{2}^{\mathrm {al}}$ as well as two ingoing vertices $v_{1}^{\mathrm {la}}$ and $v_{2}^{\mathrm {la}}$. The vertex tuples $\mathbf{v} _{1}^{\mathrm {al}}$, $\mathbf{v}_{1}^{\mathrm {la}}$ and $\mathbf{v}_{2}^{ \mathrm {al}}$, $\mathbf{v}_{2}^{\mathrm {al}}$ define line segments $j_{1}$ and $j_{2}$, respectively. The line segments together with the arcs of circle $i_{1}$ and $i_{2}$, going from vertex $v_{2}^{{\text {la}}}$ to $v_{1}^{{\text {al}}}$ and from $v_{1}^{{\text {la}}}$ to $v_{2}^{{\text {al}}}$, respectively, construct the convex hull $\partial {\mathcal {S}}$ of that arrangement. Although, circle $i_{3}$ is touching the line segment, the circle does not contribute to the convex hull and is therefore not an outer circle like circles $i_{1}$ and $i_{2}$.

Fig. 1

A configuration of four circles with two outgoing vertices $\mathbf{v}_{1}^{\mathrm {al}}$ and $\mathbf{v}_{2}^{\mathrm {al}}$ and ingoing vertices $\mathbf{v}_{1}^{\mathrm {la}}$ and $\mathbf{v}_{2}^{\mathrm {la}}$ defining the line segment $j_{1}$ and $j_{2}$ (red). Together with the arc segments (blue) of $i_{1}$ and $i_{2}$, going from $\mathbf{v}_{2}^{\mathrm { la}}$ to $\mathbf{v}_{1}^{\mathrm {al}}$ and from $\mathbf{v}_{1}^{\mathrm {la} }$ to $\mathbf{v}_{2}^{\mathrm {al}}$ the convex hull $\partial {\mathcal {S}}$ is constructed. Circles $i_{1}$ and $i_{2}$, containing the ingoing and outgoing vertices and contributing to the convex hull, are outer circles. (Color figure online)

When arranging the circles, three major constraint types have to be satisfied:

• 1. Ensure that circles do not overlap.

• 2. Fit all circles into the target domain, a rectangle of length L and width W in our case; $\mathbf{E}=(L,W)$.

• 3. Structure of ${\mathcal {S}}$ and calculating the length $\ell$ of $\partial {\mathcal {S}}$, which is the sum $\ell _{\mathrm {L}}$ of the lengths of all line segments and the sum $\ell _{\mathrm {A}}$ of the length of the arcs.

As the structure and shape of ${\mathcal {S}}$ depends on the arrangement of circles, we can also see the system of line segments touching the circles $i\in {\mathcal {I}}^{\mathrm {out}}$ as a tour between circles contributing an arc to $\partial {\mathcal {S}}$. A feasible tour can serve as the basis for the definition of the convex hull (see Sect. 2.3).

2.2 Minimal perimeter and area of the convex hull

To demonstrate the correlation between length of the perimeter $\ell$ of $\partial {\mathcal {S}}$ and area A of ${\mathcal {S}}$, let us inspect the arrangement of circles with equal unit radii 1 in Fig. 2. The packing of unit circles shown in Fig. 2a leads to a perimeter of length $\ell =$$12+2\pi$, while the perimeter of the packed circles in Fig. 2b is $\ell =8+2\pi$. The area A of ${\mathcal {S}}$ in both arrangements is equal to $12+\pi$, which is equal to the minimal area of the convex hull surrounding all four circles. To derive the area for both arrangements, we calculate the area of the minimal area rectangles hosting the circles and subtract the four difference areas of a unit square minus a quarter circle. In case (a) this yields

$$\begin{aligned} A_{\mathrm {a}}=8\cdot 2-4\left( 1-\frac{1}{4}\pi \right) =12+\pi \quad , \end{aligned}$$

which equals the result

$$\begin{aligned} A_{\mathrm {b}}=4\cdot 4-4\left( 1-\frac{1}{4}\pi \right) =12+\pi \end{aligned}$$

obtained in case (b). The example shows that minimizing the area of ${\mathcal {S}}$ does not imply that also the length of the perimeter is minimized. It remains unclear whether the minimization of $\ell$ unconditionally leads to a convex hull with minimal area. For non-circular convex hull we can only rely on the isoperimetric inequality

$$\begin{aligned} 2\pi A\le \ell ^{2}\quad . \end{aligned}$$

(2.1)

Thus, if we want to store and bind circular objects with a strap such that the minimal area on the loading area is required, we just have to minimize the perimeter of the surrounding convex hull.

Fig. 2

Two arrangements of circles both with minimal area $12+\pi$ of the convex hull but different perimeter lengths: $12+2\pi$ in case a, and $8+2\pi$ in case ba minimal convex hull area, b minimal perimeter

2.3 The convex hull and the perimeter of its boundary

In the following sections, we describe how we construct $\partial {\mathcal {S}}$ and how to calculate its length, $\ell$. In Sect. 2.3.1, we show the construction of $\partial {\mathcal {S}}$ . The relevant relations for calculating $\partial {\mathcal {S}}$ are derived in Sect. 2.3.2. The constraints required to place all circles within ${\mathcal {S}}$ are also contained in Sect. 2.3.2.

2.3.1 Characterization of the convex hull and the perimeter of its boundary

The convex hull ${\mathcal {S}}$ is the minimal convex set enclosing all circles $i\in {\mathcal {I}}$. In the MPP the position of circles are never given as, for instance, in Rapport (1992) – the positions of the circles are free in our case. To show the construction of the convex hull, let us, for now, assume that an arrangement of n non-overlapping circles placed in the plane is given. Since $\partial {\mathcal {S}}$ has minimal length, there are circles contributing an arc to $\partial {\mathcal {S}}$ (outer circles), or touching $\partial {\mathcal {S}}$ in one point only, and circles in the interior of ${\mathcal {S}}$ (inner circles), i.e., circles disjunctive to $\partial {\mathcal {S}}$. Moreover, as each point in a convex hull is part of a line segment which is also part of the convex hull ${\mathcal {S}}$, and as the convex hull is closed, the boundary $\partial {\mathcal {S}}$ consists also of straight line segments connecting the arc segments of boundary $\partial {\mathcal {S}}$ with each other. The line segments belonging to $\partial {\mathcal {S}}$ and connecting two outer circles are tangential to the arc segments being part of the boundary $\partial {\mathcal {S}}$. In Fig.  3, for example, we have an arrangement of five circles in which four circles are on the boundary of the convex hull, while one circle is in the interior of ${\mathcal {S}}$.

Fig. 3

Five circles, in which four circles $i=1,\ldots ,4,$ are on the boundary of the convex hull (outer circles) while one circle, $i=5$, is in the interior of the convex hull. The dotted lines show the direction for the construction of the convex hull. The start vertex is given by $v_1^\mathrm {al }$

Let us assume that the circles as well as the line segments defining outgoing and ingoing vertices are placed in the 2D plane. The boundary $\partial {\mathcal {S}}$ of ${\mathcal {S}}$ surrounding the circles is a planar simple closed curve (or a non-self-intersecting continuous loop in the plane, called a Jordan curve). We construct it in the following way. We start with vertex $\mathbf{v}_{1}^{\mathrm {al}}$ having the smallest dimension-1 and -2 coordinates (the x- and y-axis). The vertex is the outgoing vertex, and is tangential to the arc of that circle from which line segment ${j=1}$ leaves. Line segment ${j=1}$ ends in ingoing vertex $\mathbf{v}_{1}^{\mathrm {la}}$, which is the extreme vertex of the arc of the adjacent outer circle. The arc ends in vertex $\mathbf{v}_{2}^{\mathrm {al}}$ , which is then the outgoing vertex of line segment ${j=2}$. The line segment ends in ingoing vertex $\mathbf{v}_{2}^{\mathrm {la}}$, being the one extreme point for the arc of the directly neighbored outer circle. We continue the construction in anti-clockwise order until line segment ${j=m}$ ends in vertex $\mathbf{v}_{m}^{\mathrm {la}}$, which is the start vertex of the arc ending in vertex $\mathbf{v}_{1}^{\mathrm {al}}$. This construction closes ${\mathcal {S}}$.

Given the construction above, the length $\ell$ of $\partial {\mathcal {S}}$ is given by the sum of the lengths of line segments $\ell _{\mathrm {L}}$ and arcs $\ell _{\mathrm {A}}$. The length of outer circle i’s arc is given by the radius of circle i and the sector angle $\alpha _{ij}$ depending on the center of the circle $\mathbf{x}_{i}^{\mathrm {0}}$ and the arc defining extreme points $\mathbf{v}_{j-1}^{\mathrm {\text {la}}}$ and $\mathbf{v}_{j}^{{\text {al}}}$. Therefore, the length $\ell$ of the perimeter is calculated as

$$\begin{aligned} \ell =\ell _{\mathrm {L}}+\ell _{\mathrm {A}}\quad , \end{aligned}$$

(2.2)

with

$$\begin{aligned} \ell _{\mathrm {L}}= & {} \sum _{j}\left\| \mathbf{v}_{j}^{\mathrm {la}}- \mathbf{v}_{j}^{\mathrm {al}}\right\| _{2}=\sum _{j}\sqrt{\sum _{d}\left[ v_{dj}^{\mathrm {al}}-v_{dj}^{\mathrm {la}}\right] ^{2}} \nonumber \\ \ell _{\mathrm {A}}= & {} \sum _{ij}R_{i}\alpha _{ij}\quad , \end{aligned}$$

(2.3)

where $\ell _{\mathrm {L}}$ represents the length of the line segments while $\ell _{\mathrm {A}}$ is the sum of the lengths of all arcs. Hence, to minimize the surrounding convex hull of placed circles, we have to minimize ( 2.2).

As proven in “Appendix B.3.1”, the sum of angles $\sum _{ij}\alpha _{ij}$ of the circular sectors contributed to $\partial {\mathcal {S}}$ equals to $360^{\circ }$. Therefore, in the special case of equal radii circles, the minimal perimeter length configuration is obtained by just minimizing $\ell _{\mathrm {L}}$ as $\ell _{\mathrm {A}}$ is constant.

For two circles, we require four vertices to close the convex hull, while for $m>2$ outer circles, the number of circular arc vertices is at most 2m , i.e., where we require at most m vertices $\mathbf{v}_{j}^{ \mathrm {al}}$ and $\mathbf{v}_{j}^{\mathrm {la}}$, respectively. Since the angle of some circular arc can be also zero, we have between $2\le \max \{m,n\}$ circular arcs in general.

2.3.2 The construction of the convex hull and its boundary

In this section we show the construction of the convex hull, if the arrangement of circles is not given a priori. As the position of the circles is not known, we know neither the set of outer circles ${\mathcal {I}}^{ \mathrm {out}}$, the number of line segments m, nor the position of line segments.

The position of each circle $i\in {\mathcal {I}}$ is given by circle i’s center $\mathbf{x}_{i}^{\mathrm {0}}$ which represents the first main decision variable. To form the convex hull $\partial {\mathcal {S}}$ by means of the line segments $j\in {\mathcal {J}}$ and arcs of all outer circles (see Sect. 2.3.1), we have to set our second main decision variables, the outgoing- and ingoing vertices $\mathbf{v}_{j}^{ \mathrm {\text {al}}}$ and $\mathbf{v}_{j}^{\mathrm {\text {la}}}$, respectively (see Sect. 2.1). To indicate whether a circle i is an outer circle and establish outgoing vertex $v_{j}^{\mathrm {\text {al}}}$ of line segment $j\in {\mathcal {J}}$ we apply binary decision variable $\delta _{ij}^{\mathrm {S}}$, which is equal to one if line segment j is an outgoing tangential for source circle i, and zero otherwise. Likewise, we introduce binary variable $\delta _{ij}^{\mathrm {D}}$, which is equal to one if line segment j is an ingoing tangential for destination circle i, and zero otherwise. Finally, we use binary variable $\delta _{ij}$, which is equal to one if circle i is either a source or a destination circle of line segment j, and zero otherwise.

The length of the perimeter is calculated by the length of the line segments and arcs that form $\partial {\mathcal {S}}$ (see (2.2)). The length of an arc is dependent on the sector angle $\alpha _{ij}$ of arc (ij) on circle i. Sector angle $\alpha _{ij}$ of circle i is given by vectors $\mathbf{v}_{j-1}^{\mathrm {la}}-\mathbf{x}_{i}^{\mathrm {0}}$ and $\mathbf{v}_{j}^{\mathrm {al}}-\mathbf{x}_{i}^{\mathrm {0}}$ for $j\in \mathcal { J}$. Since inner circles do not contribute an arc to $\partial {\mathcal {S}}$, and are not source of any line segment j, i.e., $\delta _{ij}^{ \mathrm {S}}=0$, sector angle $\alpha _{ij}$ satisfies the two equations

$$\begin{aligned} R_{i}^{2}\cos \alpha _{ij}= & {} \left( \mathbf{v}_{j-1}^{\mathrm {la}}-\mathbf{x }_{i}^{\mathrm {0}}\right) \left( \mathbf{v}_{j}^{\mathrm {al}}-\mathbf{x} _{i}^{\mathrm {0}}\right) \quad ,\quad \forall \{i,j\}\quad \mathrm {\wedge } \quad \delta _{ij}^{\mathrm {S}}=1 \\ \alpha _{ij}= & {} 0\quad ,\quad \forall \{i,j\}\quad \mathrm {\wedge }\quad \delta _{ij}^{\mathrm {S}}=0\quad . \end{aligned}$$

However, at the end of this section we find an easier way to compute $\sin \alpha _{ij}$. Note that we use $\forall \{i,j\}$ as an abbreviation for $\forall \{i\in {\mathcal {I}},j\in {\mathcal {J}}\}$.

Each active line segment activates a source and a destination circle, i.e., two circles contributing an arc to $\partial {\mathcal {S}}$:

$$\begin{aligned} \sum _{i\in {\mathcal {I}}}\delta _{ij}=2\delta _{j}^{\mathrm {A}}\quad ,\quad \forall j\quad , \end{aligned}$$

(2.4)

where binary variable $\delta _{j}^{\mathrm {A}}$ indicates whether vertices $\mathbf{v}_{j}^{\mathrm {al}}$ and $\mathbf{v}_{j}^{\mathrm {la}}$ are active, i.e., line segment j is used. Note that this works pair-wise as each line segment j has an outgoing and a ingoing arc. Line segment $j+1$ can only be activated if line segment j has been activated, i.e.,

$$\begin{aligned} \delta _{j+1}^{\mathrm {A}}\le \delta _{j}^{\mathrm {A}}\quad ,\quad \forall \{j|j\le N^{\mathrm {J}}-1\}\quad , \end{aligned}$$

(2.5)

which we do to break symmetry degeneration. Activation takes place if any circle i contributes an arc to $\partial {\mathcal {S}}$, i.e.,

$$\begin{aligned} \delta _{j}^{\mathrm {A}}\ge \delta _{ij}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.6)

Note that equality (2.4) implies inequality (2.6). Therefore, (2.6) is not strictly necessary; we mention (2.6) here only for better understanding of the model.

Each line segment has a source circle arc and a destination circle arc (seen anti-clockwise). The binary variables $\delta _{ij}^{\mathrm {S}}$ and $\delta _{ij}^{\mathrm {D}}$ trace whether line segment j is connected to circle i as source or destination, i.e.,

$$\begin{aligned} \sum _{i\in {\mathcal {I}}}\delta _{ij}^{\mathrm {S}}=\delta _{j}^{\mathrm {A} }\quad ,\quad \forall j\quad , \end{aligned}$$

(2.7)

and

$$\begin{aligned} \sum _{i\in {\mathcal {I}}}\delta _{ij}^{\mathrm {D}}=\delta _{j}^{\mathrm {A} }\quad ,\quad \forall j\quad . \end{aligned}$$

(2.8)

As motivated in “Appendix B.3.2”, we enforce that each circle has at most $N_{i}^{\mathrm {ls}}$ incoming or outgoing line segment, i.e.,

$$\begin{aligned} \sum _{j\in {\mathcal {J}}}\delta _{ij}^{\mathrm {S}}\le N_{i}^{\mathrm {ls} }\quad ,\quad \forall i\quad , \end{aligned}$$

(2.9)

and

$$\begin{aligned} \sum _{j\in {\mathcal {J}}}\delta _{ij}^{\mathrm {D}}\le N_{i}^{\mathrm {ls} }\quad ,\quad \forall i\quad . \end{aligned}$$

(2.10)

For cases in which $N_{i}^{\mathrm {ls}}$ cannot be specified a priori based on geometric reasoning, we set $N_{i}^{\mathrm {ls}}=4$ as argued in “Appendix B.3.2”.

Each circle i is source or destination of a specific line segment j but not both, i.e.

$$\begin{aligned} \delta _{ij}^{\mathrm {S}}+\delta _{ij}^{\mathrm {D}}\le \delta _{j}^{\mathrm { A}}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.11)

Now we need to ensure that all circles are contained in ${\mathcal {S}}$. Our idea is: Place circle i above or below hyperplane ${\mathcal {H}}_{j}$ induced by the segment j established by the vertices $\mathbf{v}_{j}^{ \mathrm {al}}$ and $\mathbf{v}_{j}^{\mathrm {la}}$. In Hessian normal form plane ${\mathcal {H}}_{j}$ is defined by the set of all vectors $\mathbf{x}\in {\mathbb {R}}^{2}$ obeying the scalar equation $\mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{x} =d_{j}^{\mathrm {H}}$, where the normal vector $\mathbf{n}_{j}^{\mathrm {H}}$ and distance $d_{j}^{\mathrm {H}}$ to the origin of the coordinate system become additional variables as they are functions of $\mathbf{v}_{j}^{ \mathrm {al}}$ and $\mathbf{v}_{j}^{\mathrm {la}}$. In our 2D case, $\mathcal {H }_{j}$ is just the straight line connecting the vertices $\mathbf{v}_{j}^{ \mathrm {al}}$ and $\mathbf{v}_{j}^{\mathrm {la}}$. Therefore, we have the two equations

$$\begin{aligned} \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {al}}=\mathbf{n}_{j}^{ \mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {la}}=d_{j}^{\mathrm {H}}\quad ,\quad \forall j\quad . \end{aligned}$$

This implies that the normal vector $\mathbf{n}_{j}^{\mathrm {H}}$ obeys

$$\begin{aligned} \mathbf{n}_{j}^{\mathrm {H}}\cdot \left( \mathbf{v}_{j}^{\mathrm {al}}-\mathbf{v}_{j}^{\mathrm {la}}\right) =0\quad ,\quad \forall j \end{aligned}$$

which confirms our intuitive understanding that $\mathbf{n}_{j}^{\mathrm {H}}$ is orthogonal to the connecting line. Furthermore, we require that $\mathbf{n }_{j}^{\mathrm {H}}$ is normalized

$$\begin{aligned} \left\| \mathbf{n}_{j}^{\mathrm {H}}\right\| _{2}=1\quad ,\quad \forall j\quad . \end{aligned}$$

(2.12)

In the special case of our 2D geometry, we can proceed somewhat easier: Each line segment touches two circles in the vertices $\mathbf{v}_{j}^{\mathrm {al} }$ and $\mathbf{v}_{j}^{\mathrm {la}}$ in such a way that the normal vector points to the centers of those circles. The (minimal) distances of the line segments to the centers are the radii $R_{i}$ of those circles. Therefore, for the circle from which the line segment origins, we obtain a normal vector pointing from $\mathbf{v}_{j}^{\mathrm {al}}$ to $\mathbf{x}_{i}^{ \mathrm {0}}$

$$\begin{aligned} \mathbf{n}_{j}^{\mathrm {H}}=-\sum _{i\in {\mathcal {I}}}\frac{\mathbf{x}_{i}^{ \mathrm {0}}-\mathbf{v}_{j}^{\mathrm {al}}}{R_{i}}\delta _{ij}^{\mathrm {S} }\quad ,\quad \forall j\quad , \end{aligned}$$

(2.13)

and for the circle to which it leads

$$\begin{aligned} \mathbf{n}_{j}^{\mathrm {H}}=-\sum _{i\in {\mathcal {I}}}\frac{\mathbf{x}_{i}^{ \mathrm {0}}-\mathbf{v}_{j}^{\mathrm {la}}}{R_{i}}\delta _{ij}^{\mathrm {D} }\quad ,\quad \forall j\quad . \end{aligned}$$

In addition we have

$$\begin{aligned} d_{j}^{\mathrm {H}}=\mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {al}}= \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {la}}\quad ,\quad \forall j\quad . \end{aligned}$$

(2.14)

As derived in [13] we obtain the half-space separation inequalities (circle i is located on that side or half-space of ${\mathcal {H}}_{j}$ into which the normal vector $\mathbf{n}_{j}^{\mathrm {H}}$ points)

$$\begin{aligned} d_{j}^{\mathrm {H}}\ge \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{x}_{i}^{\mathrm {0} }+R_{i}\delta _{j}^{\mathrm {A}}\quad ,\quad \forall \{i,j\}\quad , \end{aligned}$$

(2.15)

if $\left\| \mathbf{n}_{j}^{\mathrm {H}}\right\| _{2}=1$ as in (2.12).

What remains to do is to model that the first m vertices out of the maximal set of $N^{\mathrm {J}}$ vertices become active and are really used to establish the convex hull, and that $\partial {\mathcal {S}}$ is closed, i.e., line segment j connects back to circle $i_{1}$. For two or three circles, we noticed that the model above can produce a “fake” solution in which the two line segments become identical with different directions, i.e., one of the two directed line segment goes from $\mathbf{v}_{j}^{\mathrm {al}}$ to $\mathbf{v}_{j}^{\mathrm {la}}$, while the other one goes from $\mathbf{v} _{j}^{\mathrm {la}}$ to $\mathbf{v}_{j}^{\mathrm {al}}$. To avoid this undesirable situation we require

$$\begin{aligned} \left\| \mathbf{v}_{j}^{\mathrm {la}}-\mathbf{v}_{j++1}^{\mathrm {al} }\right\| _{2}^{2}\ge \varepsilon \left( \delta _{j}^{\mathrm {A}}+\delta _{j++1}^{\mathrm {A}}-1\right) \quad ,\quad \forall \{j\in {\mathcal {J}}\} \end{aligned}$$

(2.16)

with $\varepsilon \approx 0.125$. Note that $j++1$ is to be understood as a circular lead operator, i.e.,

$$\begin{aligned} j\rightarrow \left\{ \begin{array}{ll}{l} j+1, \quad \\ 1,\quad \end{array} \begin{array}{l} \quad j<N^{\mathrm {J}} \\ \quad j=N^{\mathrm {J}} \end{array} \right. \quad ,\forall \{j\in {\mathcal {J}}\} \end{aligned}$$

For two circles, and other situations in which we know the number m of active line segments, (2.16) works fine, as $m=N^{\mathrm {J}}$ holds. Unfortunately, we need to exclude fake solutions also for cases in which we do not know the number of active line segments a priori, i.e., $m\le N^{\mathrm {J}}$. To cover these more general cases, we introduce binary variables $\delta _{j}^{\mathrm {L}}$ indicating whether line segment j is the last active one. Binary variable $\delta _{j}^{ \mathrm {L}}$ follows from

$$\begin{aligned} \delta _{j}^{\mathrm {L}}=\delta _{j}^{\mathrm {A}}-\delta _{j+1}^{\mathrm {A} }\quad ,\quad \forall \{j\in {\mathcal {J}}\}\quad . \end{aligned}$$

(2.17)

Furthermore, we introduce vertices $\mathbf{v}_{j}^{\mathrm {an}}$ on circular arcs which are the source of line segment $j+1$ defined as

$$\begin{aligned} \mathbf{v}_{j}^{\mathrm {an}}=\mathbf{v}_{j+1}^{\mathrm {al}}+\mathbf{v}_{1}^{ \mathrm {al}}\delta _{j}^{\mathrm {L}}\quad ,\quad \forall \{j\in {\mathcal {J}} \}\quad . \end{aligned}$$

(2.18)

As for non-active line segments the vertex variables are zero, $\delta _{j}^{ \mathrm {L}}=1$ implies $\mathbf{v}_{j+1}^{\mathrm {al}}=0$, i.e., ( 2.18) selects either $\mathbf{v}_{j+1}^{\mathrm {al}}$ or $\mathbf{v} _{1}^{\mathrm {al}}$ as the source of line segment $j+1$. Finally, we require

$$\begin{aligned} \left\| \mathbf{v}_{j}^{\mathrm {la}}-\mathbf{v}_{j}^{\mathrm {an}}\delta _{j}^{\mathrm {A}}\right\| _{2}^{2}\ge \varepsilon \delta _{j}^{\mathrm {A} }\quad ,\quad \forall \{j\in {\mathcal {J}}\} \end{aligned}$$

(2.19)

to avoid an outer circle with zero length arc.

To close $\partial {\mathcal {S}}$ we need – at least in some instances – additional half space constraints established by the two touching points $\mathbf{v}_{j}^{\mathrm {la}}$ and $\mathbf{v}_{j}^{\mathrm {an}}$ of an active circle i. Note there might be several pairs $\left( \mathbf{v}_{j}^{ \mathrm {la}},\mathbf{v}_{j}^{\mathrm {an}}\right)$ on a circle. By $\mathbf{m }_{ij}^{\mathrm {H}}$ we denote the orthogonal vector to the circle line segment connecting $\mathbf{v}_{j}^{\mathrm {la}}$ and $\mathbf{v}_{j}^{ \mathrm {an}}$ constructed as

$$\begin{aligned} \mathbf{m}_{ij}^{\mathrm {H}}= & {} \left( -v_{2j}^{\mathrm {an}}+v_{2j}^{\mathrm { la}},v_{1j}^{\mathrm {an}}-v_{1j}^{\mathrm {la}}\right) ^{\mathrm {T}}\quad ,\quad \forall \{i,j\}\mathrm {\ }\quad \wedge \quad \delta _{ij}^{\mathrm {D} }=1\quad \\ \mathbf{m}_{ij}^{\mathrm {H}}= & {} 0\quad ,\quad \forall \{i,j\}\mathrm {\ } \quad \wedge \quad \delta _{ij}^{\mathrm {D}}=0\quad , \end{aligned}$$

or equivalently

$$\begin{aligned} m_{1ij}^{\mathrm {H}}=\left( -v_{2j}^{\mathrm {an}}+v_{2j}^{\mathrm {la} }\right) \delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j\}\mathrm {\ } \end{aligned}$$

(2.20)

and

$$\begin{aligned} m_{2ij}^{\mathrm {H}}=\left( v_{1j}^{\mathrm {an}}-v_{1j}^{\mathrm {la}}\right) \delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j\}\quad .\mathrm {\ } \end{aligned}$$

(2.21)

As the scalar product of $\left( \mathbf{v}_{j}^{\mathrm {an}}-\mathbf{v} _{j}^{\mathrm {la}}\right)$ and $\mathbf{m}_{ij}^{\mathrm {H}}$ works out to be zero,

$$\begin{aligned} \left( \mathbf{v}_{j}^{\mathrm {an}}-\mathbf{v}_{j}^{\mathrm {la}}\right) \mathbf{m}_{ij}^{\mathrm {H}}=\left( v_{1j}^{\mathrm {an}}-v_{1j}^{\mathrm {la} },v_{2j}^{\mathrm {an}}-v_{2j}^{\mathrm {la}}\right) \left( \begin{array}{c} -v_{2j}^{\mathrm {an}}+v_{2j}^{\mathrm {la}} \\ v_{1j}^{\mathrm {an}}-v_{1j}^{\mathrm {la}} \end{array} \right) =0\quad ,\quad \forall \{i,j\}\quad , \end{aligned}$$

Hyperplane ${\mathcal {H}}_{ij}$ – a straight line in our 2D problem – is given by

$$\begin{aligned} {\mathcal {H}}_{ij}:=\{\mathbf{x}\in {\mathbb {R}}^{2}|\mathbf{m}_{ij}^{\mathrm {H}} \mathbf{x}=m_{ij}^{\mathrm {D}}\}\quad ,\quad \forall \{i,j\} \end{aligned}$$

with

$$\begin{aligned} m_{ij}^{\mathrm {D}}=\frac{1}{\left\| \mathbf{m}_{ij}^{\mathrm {H} }\right\| _{2}}{} \mathbf{m}_{ij}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {la} }\delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j\}\quad , \end{aligned}$$

or

$$\begin{aligned} m_{ij}^{\mathrm {D}}=\frac{1}{\left\| \mathbf{m}_{ij}^{\mathrm {H} }\right\| _{2}}{} \mathbf{m}_{ij}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {an} }\delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j\}\mathrm {\ }\quad . \end{aligned}$$

The half-space separation inequalities (circle i is located on that side of ${\mathcal {H}}_{ij}$ into which normal vector $\mathbf{m}_{ij}^{ \mathrm {H}}$ points)

$$\begin{aligned} m_{i_{s},j}^{\mathrm {D}}\ge \frac{1}{\left\| \mathbf{m}_{i_{s},j}^{ \mathrm {H}}\right\| _{2}}{} \mathbf{m}_{i_{s},j}^{\mathrm {H}}{} \mathbf{x}_{i}^{ \mathrm {0}}+R_{i}\quad ,\quad \forall \{i,i_{s}\}\mathrm {\ } \end{aligned}$$

(2.22)

enforce that all circles i are on that half-space side of circle segment $i_{s}$ directed towards the center of ${\mathcal {S}}$.

Knowing $\left\| \mathbf{m}_{i_{s},j}^{\mathrm {H}}\right\| _{2}$ enables us to derive $\alpha _{ij}$ by exploiting

$$\begin{aligned} \sin \frac{\alpha _{ij}}{2}=\frac{\left\| \mathbf{m}_{ij}^{\mathrm {H} }\right\| _{2}}{2R_{i}}\quad ,\quad \forall \{i,j\}\mathrm {\ }\quad . \mathrm {\ } \end{aligned}$$

To get $\alpha _{ij}$, we have to specify in advance whether we are expecting a major sector with $\alpha _{ij}\ge$$180^{\circ }$$(S_{ij}=1)$ or a minor sector with $\alpha _{ij}<$$180^{\circ }$$(S_{ij}=0)$. In the case of two circles, we have $S_{11}=1$ and $S_{2j}=0$, if we assume with out loss of generality that $R_{1}\ge R_{2}$ and arbritrarily assign line segment $j=1$ to circle 1 as the the outgoing line segment. In cases with one large circle and many small ones, we may also have $S_{11}=1$ and $S_{ij}=0$ for all other circles i. In most cases, we have $S_{ij}=0$ for all circles i. Using this selector flag, we obtain the sector angle $\alpha _{ij}$ in radian

$$\begin{aligned} \alpha _{ij}=2\pi S_{ij}+2(1-2S_{ij})\arcsin \left( \frac{\left\| \mathbf{m}_{ij}^{\mathrm {H}}\right\| _{2}}{2R_{i}}\right) \quad ,\quad \forall \{i,j\}\quad .\ \end{aligned}$$

2.4 Deriving the MINLP model

Based on the model constraints for the convex hull in Sect. 2.3, we introduce the final constraints for arranging circles in the plane. In Sect. 2.5 we start with the modeling of the circle packing problem irrespectively of the convex hull. An alternative formulation is presented in Sect. . In both formulations, the objective function minimizes the length of the perimeter of $\partial {\mathcal {S}}$ hosting the circles.

2.5 Packing circles

The non-overlap constraints for circles $i_{1}$ and $i_{2}$ with arbitrary radii $R_{i_{1}}$ and $R_{i_{2}}$ read

$$\begin{aligned} \left\| \mathbf{x}_{i_{1}}^{\mathrm {0}}-\mathbf{x}_{i_{2}}^{\mathrm {0} }\right\| _{2}^{2}\ge \left( R_{i_{1}}+R_{i_{2}}\right) ^{2}\quad ,\quad \forall \{i_{1},i_{2}|i_{1}<i_{2}\}\quad , \end{aligned}$$

(2.23)

with (decision variable) $x_{id}^{\mathrm {0}}$ modeling the center of circle i in dimension d. Constraints (2.23) are non-convex constraints (the left hand side constitutes a convex function). Note that for n circles we have $n(n-1)/2$ inequalities of type (2.23).

Fitting the circles inside the enclosing rectangles requires fit-the-rectangle inequalities would

$$\begin{aligned} x_{id}^{\mathrm {0}}\ge R_{i}\quad ,\quad \forall \{i,d\} \end{aligned}$$

(2.24)

and

$$\begin{aligned} x_{id}^{\mathrm {0}}+R_{i}\le E_{d}\quad ,\quad \forall \{i,d\}\quad , \end{aligned}$$

(2.25)

where $E_{d}$ specifies the length ($d=1$) and width ($d=2$) of the rectangle. Inequality (2.24) assumes that the rectangular container has its lower-left corner at the origin.

2.6 Alternative formulation

Assume a fictitious point $\mathbf{x}^{\mathrm {c}}$ inside the convex hull, for instance, the radius-weighted center

$$\begin{aligned} \mathbf{x}^{\mathrm {c}}:=\sum _{i}R_{i}{} \mathbf{x}_{i}^{\mathrm {0}}\Big / \sum _{i}R_{i} \quad . \end{aligned}$$

(2.26)

Let set ${\mathcal {J}}_{\mathrm {L}}$ have the line segments and set ${\mathcal {J}}_{\mathrm {C}}$ the circle segments. Each line segment is followed by a circle segment – we assume that counting is anti-clockwise. To each segment we assign a normal vector $\mathbf{n}_{j}^{\mathrm {H}}$ establishing the half-place ${\mathcal {H}}_{j}$

$$\begin{aligned} \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{x}=d_{j}^{\mathrm {H}}\quad ,\quad \forall \{j\in {\mathcal {J}}\}\quad . \end{aligned}$$

The normal vectors are assumed to point outside the convex hull. The normal vectors $\mathbf{n}_{j}^{\mathrm {H}}$ associated with the line segments are normalized.

$$\begin{aligned} \left\| \mathbf{n}_{j}^{\mathrm {H}}\right\| _{2}=1\quad ,\quad \forall \{j\in {\mathcal {J}}_{\mathrm {L}}\} \end{aligned}$$

(2.27)

as they are constructed according to (2.13).

The angle between line segments j and $j+1$, or the vectors $\mathbf{n} _{j}^{\mathrm {H}}$ and $\mathbf{n}_{j+1}^{\mathrm {H}}$, is in the range $[ \frac{\pi }{2},\pi ]$. Let $\mathbf{x}_{j}^{\mathrm {h}}$, $j\in {\mathcal {J}}$ , denote the half point of segment j. The angle between vectors $\mathbf{x} _{j}^{\mathrm {h}}-\mathbf{x}^{\mathrm {c}}$ and $\mathbf{n}_{j}^{\mathrm {H}}$ is in the range $[\frac{\pi }{2},\pi ]$. Vertex $\mathbf{v}_{j}^{\mathrm {la} }$ of the last active circle j segments equals $\mathbf{v}_{1}^{\mathrm {al }}$, i.e.,

$$\begin{aligned} \mathbf{v}_{1}^{\mathrm {al}}=\sum _{j}{} \mathbf{v}_{j}^{\mathrm {la}}\delta _{j}^{\mathrm {L}}\quad ,\quad \forall \{j\in {\mathcal {J}}\}\quad . \end{aligned}$$

It might also help to exploit that each circle center is located in the triangle established by the three vertices, $\mathbf{x}^{\mathrm {c}}$, the averaged center of all circles, $\mathbf{v}_{j}^{\mathrm {la}}$, the vertex arriving at some circle, and $\mathbf{v}_{j}^{\mathrm {an}}=\mathbf{v}_{j+1}^{ \mathrm {al}}$, the vertex leaving that circle. Therefore, we could represent each circle center by the convex combination

$$\begin{aligned} \mathbf{x}_{i}=\lambda _{i}^{\mathrm {c}}{} \mathbf{x}^{\mathrm {c}}+\sum _{j} \left[ \lambda _{ij}^{\mathrm {la}}{} \mathbf{v}_{j}^{\mathrm {la}}+\lambda _{ij}^{\mathrm {an}}{} \mathbf{v}_{j}^{\mathrm {an}}\right] +\sum _{j}\left[ \lambda _{ij}^{\mathrm {al}}{} \mathbf{v}_{j}^{\mathrm {al}}+\lambda _{ij}^{ \mathrm {la}}{} \mathbf{v}_{j}^{\mathrm {la}}\right] \quad ,\quad \forall \{i\in {\mathcal {I}}\}\quad . \end{aligned}$$

(2.28)

with $\lambda _{ij}^{\mathrm {c}},\lambda _{ij}^{\mathrm {la}},\lambda _{ij}^{ \mathrm {an}}\ge 0$ and the equality

$$\begin{aligned} \lambda _{i}^{\mathrm {c}}+\lambda _{ij}^{\mathrm {la}}+\lambda _{ij}^{\mathrm { an}}=\delta _{ij}^{\mathrm {t1}}+\delta _{ij}^{\mathrm {t2}}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

Note that for at most one j we have $\lambda _{i}^{\mathrm {c}}+\lambda _{ij}^{\mathrm {la}}+\lambda _{ij}^{\mathrm {an}}=1$; this is controlled by the binary variables $\delta _{ij}^{\mathrm {t1}}$ and $\delta _{ij}^{\mathrm { t2}}$ subject to

$$\begin{aligned}&\delta _{ij}^{\mathrm {t1}}+\delta _{ij}^{\mathrm {t2}}\le 1\quad ,\quad \forall \{i,j\}\quad \\&\lambda _{ij}^{\mathrm {la}}+\lambda _{ij}^{\mathrm {an}}\le \delta _{ij}^{ \mathrm {t1}}\quad ,\quad \forall \{i,j\}\quad \\&\lambda _{ij}^{\mathrm {al}}+\lambda _{ij}^{\mathrm {la}}\le \delta _{ij}^{ \mathrm {t2}}\quad ,\quad \forall \{i,j\}\quad \ \end{aligned}$$

and

$$\begin{aligned} \sum _{j}\left[ \lambda _{ij}^{\mathrm {la}}+\lambda _{ij}^{\mathrm {an}}\right] +\sum _{j}\left[ \lambda _{ij}^{\mathrm {al}}+\lambda _{ij}^{\mathrm {la}} \right] =1-\lambda _{i}^{\mathrm {c}}\quad ,\quad \forall i\quad . \end{aligned}$$

The case $\mathbf{x}_{i}=\mathbf{x}^{\mathrm {c}}$ is covered by $\lambda _{i}^{\mathrm {c}}=1$ and all other $\lambda$ having a value zero. Therefore, only one summand in (2.28) takes a non-negative value. Our hope was that this convex representation would help us to have all circles inside the convex hull or to find an easier way to construct the half-space condition of the circle segments. However, the implementation of this formulation and the results did not encourage us to follow this path further on.

2.7 Comments on the structure of the problem

The MINLP problem separates into a combinatorial, i.e., discrete part related to tours, and an NLP part if a tour has been specified and fixed. Note that a given tour also specifies the number of line segments. If no tour is specified the problem is structurally very difficult as the number of active line segments is free. Even if we would know the number m of line segments, there exist m! permutations of how to sequence them, i.e., tours. In addition to these challenges, we have to be concerned with symmetry as discussed below. A study of the convex hull for two circles is given in [15]. For a general analysis of circles in a plane see [20].

2.8 Symmetry breaking constraints

Inherent to the problem is translational and rotational symmetry. If we translate and rotate the convex hull ${\mathcal {S}}$, the length of $\partial {\mathcal {S}}$ does not change. Therefore, it would help, if we could fix, for instance, the center of the largest circle with radius R, and one line segment. Fixing the center eliminates the translational symmetry while fixing a whole line segment eliminates the rotational symmetry. In this sense, the symmetry of this optimization problem can be easier broken than in the case of circle packing when the area of the enclosing area is to be minimized; see the discussion in [11]. However, some care is necessary to fix a center and a line segment due to the rectangle fitting constraint. The cases DC03 and DC04 in the numerical experiment section allow us to fix the center coordinates and the origin vertex of the first line segment

$$\begin{aligned} \mathbf{x}_{1}=R_{1}(1,1)\quad ,\quad \mathbf{v}_{1}^{\mathrm {al} }=R_{1}(1,2)\quad , \end{aligned}$$

where $R_{1}$ is the radius of the largest circle. In this case, the largest circle is placed in the lower left corner. The first segment leaves this circle at $\mathbf{v}_{1}^{\mathrm {al}}$upwards. By doing so, we fix the orientation of the convex hull. This step is only valid if the other circles are so small that they fit above the largest circle and do not exceed the width W of the rectangle.

For target rectangles of width W and instances with one largest circle, the fixations

$$\begin{aligned} \mathbf{x}_{1}=R_{1}(1,W-1)\quad ,\quad \mathbf{v}_{1}^{\mathrm {al} }=R_{1}(1,W) \end{aligned}$$

work fine. Note that in this case the largest circle is fixed to the lower right corner of the rectangle and the first line segment is on the right side of the rectangle leaving the circle.

However, for congruent circle instances which barely fit into the target rectangle, this fixation could lose some configurations, possibly the optimal ones. One should keep in mind that this fixation fixes the orientation of the convex hull while the rectangle can reduce the possible orientations – it is always a good idea to inspect the geometry of the solution. We have exploited this fixation mainly to investigate whether we can prove global optimality faster.

2.9 Brief summary of the complete minperim model

Here we summarize the complete MinPerim model without length explanations to allow the reader to quickly grasp all the constraints. The presentation of the constraints in this section is also closer to the implementation.

2.9.1 Packing non-overlapping circles into the rectangle

The non-overlap constraints for circles $i_{1}$ and $i_{2}$ with arbitrary radii $R_{i_{1}}$ and $R_{i_{2}}$ read

$$\begin{aligned} \left\| \mathbf{x}_{i_{1}}^{\mathrm {0}}-\mathbf{x}_{i_{2}}^{\mathrm {0} }\right\| _{2}^{2}\ge \left( R_{i_{1}}+R_{i_{2}}\right) ^{2}\quad ,\quad \forall \{i_{1}i_{2}|i_{1}<i_{2}\}\quad , \end{aligned}$$

(2.29)

with (decision variable) $x_{id}^{\mathrm {0}}$ modeling the center of circle i in dimension d.

Fitting the circles inside the enclosing rectangles is ensured by

$$\begin{aligned} x_{id}^{\mathrm {0}}\ge R_{i}\quad ,\quad \forall \{i,d\} \end{aligned}$$

(2.30)

and

$$\begin{aligned} x_{id}^{\mathrm {0}}+R_{i}\le E_{d}\quad ,\quad \forall \{i,d\}\quad , \end{aligned}$$

(2.31)

where $E_{d}$ specifies the length ($d=1$) and width ($d=2$) of the rectangle.

2.9.2 Boundary of the convex hull: line segments

The objective function to be minimized is the length $\ell$ of the perimeter of the convex hull

$$\begin{aligned} \ell =\sum _{j\in {\mathcal {J}}}\sqrt{\sum _{d\in {\mathcal {D}}}\left[ v_{dj}^{ \mathrm {al}}-v_{dj}^{\mathrm {la}}\right] ^{2}}+\sum _{i\in {\mathcal {I}} }\sum _{j\in {\mathcal {J}}}R_{i}\alpha _{ij}\quad . \end{aligned}$$

(2.32)

Each line segment has a source circle arc and a destination circle arc (seen anti-clockwise). The binary variables $\delta _{ij}^{\mathrm {S}}$ and $\delta _{ij}^{\mathrm {D}}$ trace whether line segment j is connected to circle i as source or destination, i.e.,

$$\begin{aligned} \sum _{i\in {\mathcal {I}}}\delta _{ij}^{\mathrm {S}}=\delta _{j}^{\mathrm {A} }\quad ,\quad \forall j\quad , \end{aligned}$$

(2.33)

and

$$\begin{aligned} \sum _{i\in {\mathcal {I}}}\delta _{ij}^{\mathrm {D}}=\delta _{j}^{\mathrm {A} }\quad ,\quad \forall j\quad . \end{aligned}$$

(2.34)

Each circle i is source or destination of a specific line segment j but not both, i.e.

$$\begin{aligned} \delta _{ij}^{\mathrm {S}}+\delta _{ij}^{\mathrm {D}}\le \delta _{j}^{\mathrm { A}}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.35)

Note that in connection with (2.35), (2.33) and ( 2.34), assign an active line segment j to two circles, a source circle and a destination circle.

We enforce that each circle has at most $N_{i}^{\mathrm {ls}}$ incoming or outgoing line segment, i.e.,

$$\begin{aligned} \sum _{j\in {\mathcal {J}}}\delta _{ij}^{\mathrm {S}}\le N_{i}^{\mathrm {ls} }\quad ,\quad \forall i\quad , \end{aligned}$$

(2.36)

and

$$\begin{aligned} \sum _{j\in {\mathcal {J}}}\delta _{ij}^{\mathrm {D}}\le N_{i}^{\mathrm {ls} }\quad ,\quad \forall i\quad . \end{aligned}$$

(2.37)

Integer variable $\mu$ counts the number of active line segments

$$\begin{aligned} \mu =\sum _{j\in {\mathcal {J}}}\delta _{j}^{\mathrm {A}}\quad . \end{aligned}$$

(2.38)

Each active line segment activates two circles contributing an arc to $\partial {\mathcal {S}}$:

$$\begin{aligned} \sum _{i\in {\mathcal {I}}}\delta _{ij}=2\delta _{j}^{\mathrm {A}}\quad ,\quad \forall j\quad . \end{aligned}$$

(2.39)

Line segment $j+1$ can only be activated if line segment j has been activated, i.e.,

$$\begin{aligned} \delta _{j+1}^{\mathrm {A}}\le \delta _{j}^{\mathrm {A}}\quad ,\quad \forall \{j|j\le N^{\mathrm {J}}-1\}\quad , \end{aligned}$$

(2.40)

which breaks symmetry degeneration. Activation takes place, if any circle i contributes an arc to $\partial {\mathcal {S}}$, i.e.,

$$\begin{aligned} \delta _{j}^{\mathrm {A}}\ge \delta _{ij}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.41)

To avoid zero length arcs we require

$$\begin{aligned} \left\| \mathbf{v}_{j}^{\mathrm {la}}-\mathbf{v}_{j++1}^{\mathrm {al} }\right\| _{2}^{2}\ge \varepsilon \left( \delta _{j}^{\mathrm {A}}+\delta _{j++1}^{\mathrm {A}}-1\right) \quad ,\quad \forall j \end{aligned}$$

(2.42)

with $\varepsilon \approx 0.125$. Note that $j++1$ is to be understood as a circular lead operator, i.e.,

$$\begin{aligned} j\rightarrow \left\{ \begin{array}{ll} j+1, \quad \\ 1,\quad \end{array} \begin{array}{c} \quad j<N^{\mathrm {J}} \\ \quad j=N^{\mathrm {J}} \end{array} \right. \quad ,\quad \forall j\quad . \end{aligned}$$

Binary variables $\delta _{j}^{\mathrm {L}}$ indicating whether line segment j is the last active one follows from

$$\begin{aligned} \delta _{j}^{\mathrm {L}}=\delta _{j}^{\mathrm {A}}-\delta _{j+1}^{\mathrm {A} }\quad ,\quad \forall j\quad . \end{aligned}$$

(2.43)

Furthermore, we introduce vertices $\mathbf{v}_{j}^{\mathrm {an}}$ on circular arcs which are the origin of line segment $j+1$ defined as

$$\begin{aligned} \mathbf{v}_{j}^{\mathrm {an}}=\mathbf{v}_{j+1}^{\mathrm {al}}+\mathbf{v}_{1}^{ \mathrm {al}}\delta _{j}^{\mathrm {L}}\quad ,\quad \forall j\quad . \end{aligned}$$

(2.44)

Note that $\delta _{j}^{\mathrm {L}}=1$ implies $\mathbf{v}_{j+1}^{\mathrm {al} }=0$, i.e., (2.18) selects either $\mathbf{v}_{j+1}^{ \mathrm {al}}$ or $\mathbf{v}_{1}^{\mathrm {al}}$ as the origin of line segment $j+1$. Finally, we require

$$\begin{aligned} \left\| \mathbf{v}_{j}^{\mathrm {la}}-\sum _{i}{} \mathbf{v}_{j}^{\mathrm {an} }\delta _{ij}^{\mathrm {D}}\right\| _{2}^{2}\ge \varepsilon \delta _{j}^{ \mathrm {A}}\quad ,\quad \forall j\quad . \end{aligned}$$

(2.45)

The normal vector $\mathbf{n}_{j}^{\mathrm {H}}$ on line segment j follows from

$$\begin{aligned} n_{dj}^{\mathrm {H}}=-\sum _{i\in {\mathcal {I}}}\frac{x_{id}^{\mathrm {0} }-v_{dj}^{\mathrm {al}}}{R_{i}}\delta _{ij}^{\mathrm {S}}\quad ,\quad \forall \{d,j\}\quad . \end{aligned}$$

(2.46)

It is normalized to unity if the line segment j is activated

$$\begin{aligned} \sum _{d\in {\mathcal {D}}}\left( n_{dj}^{\mathrm {H}}\right) ^{2}=\delta _{j}^{ \mathrm {A}}\quad ,\quad \forall j\quad . \end{aligned}$$

(2.47)

The outgoing and ingoing vertices $\mathbf{v}_{j}^{\mathrm {al}}$ and $\mathbf{v}_{j}^{\mathrm {la}}$ of line segment j are on hyperplane ${\mathcal {H}}_{j}$, i.e., on the line connecting both vertices

$$\begin{aligned} d_{j}^{\mathrm {H}}= & {} \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {al} }\quad ,\quad \forall j\quad , \end{aligned}$$

(2.48)

$$\begin{aligned} d_{j}^{\mathrm {H}}= & {} \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{v}_{j}^{\mathrm {la} }\quad ,\quad \forall j\quad . \end{aligned}$$

(2.49)

The vertices are set to zero, if line segment j ist not active

$$\begin{aligned} v_{dj}^{\mathrm {al}}\le & {} E_{d}\delta _{j}^{\mathrm {A}}\quad ,\quad \forall \{d,j\}\quad , \end{aligned}$$

(2.50)

$$\begin{aligned} v_{dj}^{\mathrm {la}}\le & {} E_{d}\delta _{j}^{\mathrm {A}}\quad ,\quad \forall \{d,j\}\quad . \end{aligned}$$

(2.51)

Note that the size $E_{d}$ of the rectangle in direction d provides the smallest valid upper bound.

Half-space separation inequalities (circle i is located on that side or half-space of ${\mathcal {H}}_{j}$ into which the normal vector $\mathbf{n}_{j}^{\mathrm {H}}$ points)

$$\begin{aligned} d_{j}^{\mathrm {H}}\ge \mathbf{n}_{j}^{\mathrm {H}}{} \mathbf{x}_{i}^{\mathrm {0} }+R_{i}\delta _{j}^{\mathrm {A}}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.52)

2.9.3 Constraints for computing the circle segments

By $\mathbf{m}_{ij}^{\mathrm {H}}$ we denote the orthogonal vector onto the circle line segment of circle i connecting $\mathbf{v}_{j}^{ \mathrm {la}}$ and $\mathbf{v}_{j}^{\mathrm {an}}$ constructed as

$$\begin{aligned} m_{1ij}^{\mathrm {H}}= & {} \left( -v_{2j}^{\mathrm {an}}+v_{2j}^{\mathrm {la} }\right) \delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j\} \end{aligned}$$

(2.53)

$$\begin{aligned} m_{2ij}^{\mathrm {H}}= & {} \left( v_{1j}^{\mathrm {an}}-v_{1j}^{\mathrm {la} }\right) \delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.54)

Its norm $\left\| \mathbf{m}_{ij}^{\mathrm {H}}\right\| _{2}$ follows from the quadratic equality

$$\begin{aligned} \left\| \mathbf{m}_{ij}^{\mathrm {H}}\right\| _{2}^{2}=\left( m_{1ij}^{ \mathrm {H}}\right) ^{2}+\left( m_{2ij}^{\mathrm {H}}\right) ^{2}\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.55)

The right-hand side value of the Hessian normal form $\mathbf{m}_{ij}^{ \mathrm {H}}{} \mathbf{x}=m_{ij}^{\mathrm {D}}$ is computed as

$$\begin{aligned} \left\| \mathbf{m}_{ij}^{\mathrm {H}}\right\| _{2}m_{ij}^{\mathrm {D} }=\sum _{d}m_{dij}^{\mathrm {H}}v_{dj}^{\mathrm {la}}\delta _{ij}^{\mathrm {D} }\quad ,\quad \forall \{i,j\}\quad . \end{aligned}$$

(2.56)

The half-space separation inequalities (circle i is located on that side or half-space of ${\mathcal {H}}_{ij}$ into which normal vector $\mathbf{m}_{ij}^{\mathrm {H}}$ points)

$$\begin{aligned} m_{i_{s},j}^{\mathrm {D}}\ge \frac{1}{\left\| \mathbf{m}_{i_{s},j}^{ \mathrm {H}}\right\| _{2}}{} \mathbf{m}_{i_{s}j}^{\mathrm {H}}{} \mathbf{x}_{i}^{ \mathrm {0}}+R_{i}\quad ,\quad \forall \{i,i_{s},j\}\mathrm {\ } \end{aligned}$$

(2.57)

enforce that all circles i are on that half-space side of circle segment $(i_{s},j)$ directed approximately towards the center of ${\mathcal {S}}$.

2.9.4 Constraints for computing the lengths of the circular arcs

Computing the lengths of the circular arcs requires all constraints listed in Sect. 2.9.3 and in addition the following equalities. Knowing $\left\| \mathbf{m}_{i_{s},j}^{\mathrm {H}}\right\| _{2}$ enables us to derive $\alpha _{ij}$ by exploiting

$$\begin{aligned} \sin \frac{\alpha _{ij}}{2}=\frac{\left\| \mathbf{m}_{ij}^{\mathrm {H} }\right\| _{2}}{2R_{i}}\quad ,\quad \forall \{i,j\}\mathrm {\ } \end{aligned}$$

(2.58)

and

$$\begin{aligned} \alpha _{ij}=2\pi S_{ij}+2(1-2S_{ij})\arcsin \left( \frac{\left\| \mathbf{m}_{ij}^{\mathrm {H}}\right\| _{2}}{2R_{i}}\right) \quad ,\quad \forall \{i,j\}\quad .\ \end{aligned}$$

(2.59)

2.9.5 Cut: valid inequalities

To improve the numerical performance, we considered the following valid inequalities. If line segment j enters circular arc i, then line segment $j+1$ will leave circle i, i.e.,

$$\begin{aligned} \delta _{i,j+1}^{\mathrm {S}}+\delta _{i1}^{\mathrm {S}}\ge & {} \delta _{ij}^{ \mathrm {D}}\quad ,\quad \forall \{i,j|j<N^{\mathrm {J}}\}\quad , \end{aligned}$$

(2.60)

$$\begin{aligned} \ \delta _{i1}^{\mathrm {S}}\ge & {} \delta _{ij}^{\mathrm {D}}\quad ,\quad \forall \{i,j|j=N^{\mathrm {J}}\}\quad . \end{aligned}$$

(2.61)

Unfortunately, in our numerical experiments they did not turn out to be useful.

3 Analytic solutions

Analytical solutions are computed for the unrestricted case only, i.e. fit-the-rectangle inequalities (2.24) and (2.25) are relaxed. As in this case, each circle contributes at most one arc to the boundary of the convex hull, for simplicity of reading, in this section we neglect the index of the angles referring to line segments.

3.1 Two circles

As displayed in Fig. 4, active line segments touch the circles in points which form a right angle between the line segment and the line towards the center of the circle. Therefore, the line segment connecting two touching circles can be described by a right-angled trapezium (trapezoid) which yields by Pythagoras’ theorem

$$\begin{aligned} \ell _{\mathrm {tc}}=\sqrt{(R_{1}+R_{2})^{2}-(R_{1}-R_{2})^{2}}=2\sqrt{ R_{1}R_{2}}\quad . \end{aligned}$$

(3.1)

Thus both line segments contribute a length of

$$\begin{aligned} \ell _{\mathrm {L}2}=2\ell _{\mathrm {tc}}=4\sqrt{R_{1}R_{2}} \end{aligned}$$

(3.2)

to $\partial {\mathcal {S}}$. For the case $R_{1}\ge R_{2}$ (see Fig. 4), the center coordinates of both circles are

$$\begin{aligned} \mathbf{x}_{1}= & {} R_{1}(1,1)\quad , \\ \mathbf{x}_{2}= & {} \mathbf{x}_{1}+(R_{1}+R_{2},0)=(2R_{1}+R_{2},R_{1})\quad , \end{aligned}$$

while the angles, $\alpha _{1}$ and $\alpha _{2}$, of the circular sectors are

$$\begin{aligned} \alpha _{1}=2\pi -2\arccos \frac{R_{1}-R_{2}}{R_{1}+R_{2}}\quad ,\quad \alpha _{2}=2\arccos \frac{R_{1}-R_{2}}{R_{1}+R_{2}} \end{aligned}$$

(3.3)

or, alternatively,

$$\begin{aligned} \alpha _{1,2}=\pi \pm 2\arccos \frac{2\sqrt{R_{1}R_{2}}}{R_{1}+R_{2}}\quad , \end{aligned}$$

and thus, the length $\ell _{2}$ of $\partial {\mathcal {S}}$ of two touching circles is given by

$$\begin{aligned} \ell _{2}=\ell _{\mathrm {L}2}+\ell _{\mathrm {A}2}=4\sqrt{R_{1}R_{2}} +R_{1}\alpha _{1}+R_{2}\alpha _{2}\quad . \end{aligned}$$

(3.4)

Note that $R_{2}=R_{1}=R$ implies $\alpha _{2}=\alpha _{1}=\pi$, i.e. , the contributed length $\ell _{\mathrm {A}2}$ of the arcs is $2\pi R$ as geometrically expected.

Fig. 4

Arrangement of two circles for $R_{1}\ge R_{2}$ with connecting line segment $\ell _{\mathrm {tc}}$

Let us now find the vertex points, $\mathbf{v}_{i}={(v_{i1},v_{i2})}$ , $i\in \{1,2\}$, on two circles with center coordinates $\mathbf{x}_{i}={(x} _{i1},x_{i2})$. Note that we currently do not assume that both circles touch each other. The line segment connecting circle 1 and circle 2 is part of the outer tangent.

The touching points $\mathbf{v}_{i}$ can be expressed as a function of $\mathbf{x}_{i}$ and angle $\alpha$

$$\begin{aligned} {v_{i1}}= & {} x_{i1}+R_{i}\cos \left( \frac{\pi }{2}-\alpha \right) \\ {v_{i2}}= & {} x_{i2}+R_{i}\sin \left( \frac{\pi }{2}-\alpha \right) \end{aligned}$$

with

$$\begin{aligned} \alpha ={\gamma -\beta }\quad ,\quad \gamma =\arctan \left( \frac{ x_{12}-x_{22}}{x_{21}-x_{11}}\right) \quad ,\quad {\beta =\arcsin \left( \frac{R_{1}-R_{2}}{d}\right) \quad ,} \end{aligned}$$

where d denotes the distance between the circular centers, i.e.,

$$\begin{aligned} {d=}\sqrt{(x_{21}-x_{11})^{2}+(x_{22}-x_{12})^{2}}{\quad ;} \end{aligned}$$

(3.5)

cf. [3] or [14].

3.2 Three circles

For three circles with $R_{1}\ge R_{2}\ge R_{3}$ we have to distinguish two cases: A) Circle 3 with radius $R_{3}$ is so small that it fits into the gaps between the two larger circles. In that case, the sum of the lengths of the line segments is again $\ell _{\mathrm {L}2}$ as in the case of two circles. B) Circle 3 does not fit into a gap: Then the minimal sum of the lengths of the line segments is given by

$$\begin{aligned} \ell _{\mathrm {L}3}=2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{3}}+\sqrt{ R_{3}R_{1}}\right] \quad . \end{aligned}$$

(3.6)

To derive the center coordinates, let us place circle 1 with the largest radius at position

$$\begin{aligned} \mathbf{x}_{1}=(R_{1},W-R_{1})\quad , \end{aligned}$$

where W denotes the width of the target rectangle (see Fig. 5).

Fig. 5

Arrangement of circle 1 with $\mathbf{x}_{1}=(R_{1},W-R_{1})$ in the target box with dimension $E=(L,W).$

The other centers follow from the touching conditions

$$\begin{aligned} \left\| \mathbf{x}_{i_{1}}-\mathbf{x}_{i_{2}}\right\| _{2}=R_{i_{1}}+R_{i_{2}}\quad ,\quad \forall \{i_{1},i_{2}|i_{1}<i_{2}\}\quad . \end{aligned}$$

(3.7)

Thus, we know three sides

$$\begin{aligned} a= & {} R_{2}+R_{3} \\ b= & {} R_{3}+R_{1} \\ c= & {} R_{1}+R_{2} \end{aligned}$$

in the triangle established by the three circle centers and can derive the angles

$$\begin{aligned} \alpha= & {} \arccos \left( \frac{b {{}^2} +c {{}^2} -a {{}^2} }{2bc}\right) =\arccos \left( \frac{ (R_{3}+R_{1})^{2}+(R_{1}+R_{2})^{2}-(R_{2}+R_{3})^{2}}{ 2(R_{3}+R_{1})(R_{1}+R_{2})}\right) \\= & {} \arccos \left( \frac{R_{1}R_{2}+R_{1}R_{3}-R_{2}R_{3}+R_{1}^{2}}{ (R_{3}+R_{1})(R_{1}+R_{2})}\right) \\ \beta= & {} \arccos \left( \frac{a {{}^2} +c {{}^2} -b {{}^2} }{2ac}\right) \\ \gamma= & {} \arccos \left( \frac{a {{}^2} +b {{}^2} -c {{}^2} }{2ab}\right) \quad . \end{aligned}$$

To break rotational symmetry of the configuration, we fix line segment $j=1$ at $(R_{1},W)$ at circle 1, which leads to the following position for the center of circle 2 at

$$\begin{aligned} \mathbf{x}_{2}= & {} \left( x_{11}+\sqrt{\left( R_{1}+R_{2}\right) ^{2}-\left( x_{22}-x_{12}\right) ^{2}},W-R_{2}\right) \\= & {} \left( R_{1}+\sqrt{\left( R_{1}+R_{2}\right) ^{2}-\left( W-R_{1}-\left( W-R_{2}\right) \right) ^{2}},W-R_{2}\right) \\= & {} \left( R_{1}+2\sqrt{R_{1}R_{2}},W-R_{2}\right) \quad . \end{aligned}$$

We can try to derive $\mathbf{x}_{3}$ from the conditions

$$\begin{aligned} \left\| \mathbf{x}_{3}-\mathbf{x}_{2}\right\| _{2}^{2}= & {} (x_{31}-x_{21})^{2}+(x_{32}-x_{22})^{2}=\left( R_{2}+R_{3}\right) ^{2} \\ \left\| \mathbf{x}_{3}-\mathbf{x}_{1}\right\| _{2}^{2}= & {} (x_{31}-x_{11})^{2}+(x_{32}-x_{12})^{2}=\left( R_{1}+R_{3}\right) ^{2}\ \end{aligned}$$

leading to

$$\begin{aligned} x_{21}^{2}-2x_{22}x_{32}-2x_{21}x_{31}+x_{22}^{2}+x_{31}^{2}+x_{32}^{2}= & {} \left( R_{2}+R_{3}\right) ^{2} \end{aligned}$$

(3.8)

$$\begin{aligned} x_{11}^{2}-2x_{12}x_{32}-2x_{11}x_{31}+x_{12}^{2}+x_{31}^{2}+x_{32}^{2}= & {} \left( R_{1}+R_{3}\right) ^{2}\quad . \end{aligned}$$

(3.9)

Unfortunately, taking the difference of (3.8) and (3.9) leads to only one linear equation for the two unknown variables $x_{31}$ and $x_{32}$

$$\begin{aligned} 2(x_{11}-x_{21})x_{31}+2(x_{12}-x_{22})x_{32}-x_{11}^{2}-x_{12}^{2}+ x_{21}^{2}+x_{22}^{2}=2R_{2}R_{3}-2R_{1}R_{3}+R_{2}^{2}-R_{1}^{2}\quad . \end{aligned}$$

Therefore, we take a different route exploiting various trigonometric relations. Identify the vertices A, B, and C, of the triangle with the center of the circles 1, 2 and 3. The coordinates of $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are known from above. With respect to a coordinate system with origin $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ on the positive x-axis, C, i.e., the center of the coordinates of circle 3, has coordinates

$$\begin{aligned} \mathbf{x}_{3}^{\prime }=(R_{1}+R_{3})\left( \begin{array}{c} \cos \alpha \\ \sin \alpha \end{array} \right) \quad . \end{aligned}$$

With

$$\begin{aligned} \cos \varphi _{3}:=\frac{(1,0)(\mathbf{x}_{2}-\mathbf{x}_{1})}{\left\| \mathbf{x}_{2}-\mathbf{x}_{1}\right\| _{2}}=\frac{x_{22}-x_{12}}{ R_{1}+R_{2}} \end{aligned}$$

we, finally, get the coordinates of the center of circle 3

$$\begin{aligned} \mathbf{x}_{3}=\mathbf{x}_{1}+\left( \begin{array}{cc} \cos \varphi _{3} &{} \sin \varphi _{3} \\ -\sin \varphi _{3} &{} \cos \varphi _{3} \end{array} \right) \mathbf{x}_{3}^{\prime }=\mathbf{x}_{1}+\left( \begin{array}{cc} \cos \varphi _{3} &{} \sqrt{1-\cos ^{2}\varphi _{3}} \\ -\sqrt{1-\cos ^{2}\varphi _{3}} &{} \cos \varphi _{3} \end{array} \right) \mathbf{x}_{3}^{\prime }\quad . \end{aligned}$$

Note that we exploit this result also in the next section deriving the analytic solution for four circles.

To answer the question of the maximal size of $R_{3}$ which allows circle 3 to fit in the interior of ${\mathcal {S}}$, we solve (3.7) for a slightly different placement of the spheres. Without loss of generality, we place

$$\begin{aligned} \mathbf{x}_{1}^{\mathrm {0}}=(x_{11},x_{12})^{\mathrm {T}}=(R_{1},R_{1})^{ \mathrm {T}} \end{aligned}$$

(3.10)

$$\begin{aligned} \mathbf{x}_{2}^{\mathrm {0}}=(x_{21},2R_{1}-R_{2})^{\mathrm {T}}\quad . \end{aligned}$$

(3.11)

This placement implies: If $x_{32}+R_{3}>2R_{1}$, circle 3 does not fit in the interior of ${\mathcal {S}}$. In this configuration, circle 3 just touches the line segment connecting circle 1 and circle 2; the line segment is parallel to the $x_{1}$-axis. For all configurations $R_{1}\ge R_{2}\ge R_{3}$ and $R_{3}\le 2R_{1}$, circle 3 fits in the interior of ${\mathcal {S}}$ . As we will see, the limit case $x_{32}=2R_{1}-R_{3}$ requires

$$\begin{aligned} R_{3}=\frac{1}{4}R_{1}\vee R_{3}=\frac{R_{1}R_{2}}{R_{1}+2\sqrt{R_{1}R_{2}} +R_{2}}\quad . \end{aligned}$$

This follows from the three equations to be solved for $x_{21}$, $x_{31}$ and $x_{32}=2R_{1}-R_{3}$:

$$\begin{aligned} \left\| \mathbf{x}_{2}-\mathbf{x}_{1}\right\| _{2}^{2}= & {} (x_{21}-x_{11})^{2}+(x_{22}-x_{12})^{2}=\left( R_{1}+R_{2}\right) ^{2} \\ \left\| \mathbf{x}_{3}-\mathbf{x}_{2}\right\| _{2}^{2}= & {} (x_{31}-x_{21})^{2}+(x_{32}-x_{22})^{2}=\left( R_{2}+R_{3}\right) ^{2} \\ \left\| \mathbf{x}_{3}-\mathbf{x}_{1}\right\| _{2}^{2}= & {} (x_{31}-x_{11})^{2}+(x_{32}-x_{12})^{2}=\left( R_{1}+R_{3}\right) ^{2}\ \end{aligned}$$

or

$$\begin{aligned} \left\| \mathbf{x}_{2}-\mathbf{x}_{1}\right\| _{2}^{2}= & {} (x_{21}-R_{1})^{2}+(2R_{1}-R_{2}-R_{1})^{2}=\left( R_{1}+R_{2}\right) ^{2} \end{aligned}$$

(3.12)

$$\begin{aligned} \left\| \mathbf{x}_{3}-\mathbf{x}_{2}\right\| _{2}^{2}= & {} (x_{31}-x_{21})^{2}+(x_{32}-2R_{1}+R_{2})^{2}=\left( R_{2}+R_{3}\right) ^{2} \end{aligned}$$

(3.13)

$$\begin{aligned} \left\| \mathbf{x}_{3}-\mathbf{x}_{1}\right\| _{2}^{2}= & {} \ (x_{31}-R_{1})^{2}+(x_{32}-R_{1})^{2}=\left( R_{1}+R_{3}\right) ^{2}\quad . \end{aligned}$$

(3.14)

The first equation (3.12) gives us

$$\begin{aligned} x_{21}=\sqrt{\left( R_{1}+R_{2}\right) ^{2}-(2R_{1}-R_{2}-R_{1})^{2}}=R_{1}+2 \sqrt{R_{1}R_{2}}\quad . \end{aligned}$$

We solve the other two equations, (3.13) and (3.14), for $x_{31}$ and obtain

$$\begin{aligned} x_{31}= & {} x_{21}-\sqrt{\left( R_{2}+R_{3}\right) ^{2}-(x_{32}-2R_{1}+R_{2})^{2}} \\ x_{31}= & {} x_{11}+\sqrt{\left( R_{1}+R_{3}\right) ^{2}-(x_{32}-R_{1})^{2}} \end{aligned}$$

and finally

$$\begin{aligned} x_{31}= & {} x_{21}-2\sqrt{R_{2}R_{3}}=R_{1}+2\sqrt{R_{1}R_{2}}-2\sqrt{ R_{2}R_{3}} \\ x_{31}= & {} x_{11}+2\sqrt{R_{1}R_{3}}=R_{1}+2\sqrt{R_{1}R_{3}}\quad , \end{aligned}$$

which leads to the condition

$$\begin{aligned} \sqrt{R_{1}R_{2}}-\sqrt{R_{2}R_{3}}=\sqrt{R_{1}R_{3}}\quad , \end{aligned}$$

and is generally true for $R_{3}=\frac{1}{4}R_{1}$. In all other cases we obtain

$$\begin{aligned} R_{3}=\frac{R_{1}R_{2}}{R_{1}+2\sqrt{R_{1}R_{2}}+R_{2}}\quad . \end{aligned}$$

If $x_{32}<2R_{1}-R_{3}$, the three circles can still touch each other but we have to obtain $x_{32}$ from the equation

$$\begin{aligned}&2\sqrt{R_{1}R_{2}}-\sqrt{\left( R_{2}+R_{3}\right) ^{2}-(x_{32}-2R_{1}+R_{2})^{2}}=\sqrt{\left( R_{1}+R_{3}\right) ^{2}-(x_{32}-R_{1})^{2}}\quad .\\&2\sqrt{R_{1}R_{1}}-\sqrt{\left( R_{1}+R_{3}\right) ^{2}-(x_{32}-2R_{1}+R_{1})^{2}}=\sqrt{\left( R_{1}+R_{3}\right) ^{2}-(x_{32}-R_{1})^{2}}\quad . \end{aligned}$$

A general solution independent of $R_{2}$ is

$$\begin{aligned} x_{32}=R_{1}-\sqrt{2R_{1}R_{3}+R_{3}^{2}}\quad . \end{aligned}$$

For $R_{1}>R_{2}$, the solution is

$$\begin{aligned} x_{32}=\frac{ 2R_{1}^{3}-2R_{1}R_{2}R_{3}+2R_{1}^{2}R_{2}+R_{1}^{2}R_{3}+R_{2}^{2}R_{3}-4 \sqrt{R_{1}R_{2}}\sqrt{R_{1}R_{2}R_{3}\left( R_{1}+R_{2}+R_{3}\right) }}{ \left( R_{1}+R_{2}\right) ^{2}}\end{aligned}$$

Without loss of generality, we can fix the $x_{2}$-coordinates $x_{12},x_{22}=0$ for circles 1 and 2. We further fix $x_{11}=0$, i.e. , circle 1 is placed at (0, 0, 0). This leaves us with three unknown variables $x_{21},x_{31}$, and$\ x_{22}$ leading to the somewhat simpler looking solution

$$\begin{aligned} \mathbf{x}_{1}^{\mathrm {0}}= & {} (x_{11},x_{12})^{\mathrm {T}}=(R_{1},R_{1})^{ \mathrm {T}} \end{aligned}$$

(3.15)

$$\begin{aligned} \mathbf{x}_{2}^{\mathrm {0}}= & {} (2R_{1}+R_{2},R_{1})^{\mathrm {T}} \end{aligned}$$

(3.16)

$$\begin{aligned} \mathbf{x}_{3}^{\mathrm {0}}= & {} \left( R_{1}+\frac{ R_{1}R_{2}+R_{1}R_{3}-R_{2}R_{3}+R_{1}^{2}}{R_{1}+R_{2}},R_{1}+\frac{2\sqrt{ R_{1}R_{2}R_{3}\left( R_{1}+R_{2}+R_{3}\right) }}{R_{1}+R_{2}} \right) ^{\mathrm {T}},\qquad \quad \end{aligned}$$

(3.17)

but it is not easy to see whether circle 3 is located in the interior of ${\mathcal {S}}$.

3.3 Four circles

For four circles, the minimal configuration is connected to one of the tour formula

$$\begin{aligned} \ell _{\mathrm {L}4}^{(1)}= & {} 2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{3}}+\sqrt{ R_{3}R_{4}}+\sqrt{R_{4}R_{1}}\right] \quad , \end{aligned}$$

(3.18)

$$\begin{aligned} \ell _{\mathrm {L}4}^{(2)}= & {} 2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{4}}+\sqrt{ R_{4}R_{3}}+\sqrt{R_{3}R_{1}}\right] \quad , \end{aligned}$$

(3.19)

or

$$\begin{aligned} \ell _{\mathrm {L}4}^{(3)}=2\left[ \sqrt{R_{1}R_{3}}+\sqrt{R_{3}R_{2}}+\sqrt{ R_{2}R_{4}}+\sqrt{R_{4}R_{1}}\right] \quad . \end{aligned}$$

(3.20)

Note that each of them represents a tour. Without loss of generality, we start tours at circle 1. This gives $3!=6$ tours from which we can neglect half, as they just represent the tours in reversed order, i.e., it is sufficient to consider just these three tours 1-2-3-4-1, 1-2-4-3-1, and 1-3-2-4-1.

If circle 4 is so small that it fits into the interior of ${\mathcal {S}}$, we obtain $\ell _{\mathrm {L}4}=\ell _{\mathrm {L}3}$, and if circles 3 and 4 both fit into the interior of ${\mathcal {S}}$, we can even have $\ell _{ \mathrm {L}4}=\ell _{\mathrm {L}2}$.

To derive the center coordinates, let us assume that $R_{1}\ge R_{2}\ge R_{3}\ge R_{4}$ with the largest circle placed at

$$\begin{aligned} \mathbf{x}_{1}=(R_{1},W-R_{1})\quad . \end{aligned}$$

If all circles contribute an arc to $\partial {\mathcal {S}}$, numerically we find that for our example case DC04 the optimal tour providing minimal $\ell$ is given by 1-3-2-4, i.e., we travel counter-clockwise from circle 1, to circle 3, to 2, to 4 and back to 1. If minimal $\ell _{\mathrm {L}}$ is necessary for minimal $\ell$, we could select the minimal tour from one of the formula (3.18) to (3.20). As we have not proven this, we numerically evaluate all three tours using the MinPerim model to select the tour with minimal $\ell$.

Similar as in the case of three circles, we break rotational symmetry of the configuration by fixing line segment $j=1$ at $(R_{1},W)$ at circle 1, which leads to the following position for the center of circle 3 at

$$\begin{aligned} \mathbf{x}_{3}= & {} \left( x_{11}+\sqrt{\left( R_{1}+R_{3}\right) ^{2}-\left( x_{32}-x_{12}\right) ^{2}},W-R_{3}\right) \\= & {} \left( R_{1}+2\sqrt{R_{1}R_{3}},W-R_{3}\right) \quad . \end{aligned}$$

Following the same procedure as for three circles, we obtain for circle 2 the following center coordinates

$$\begin{aligned} \mathbf{x}_{2}^{\prime }= & {} (R_{1}+R_{3})\left( \begin{array}{c} \cos \alpha _{4}^{1} \\ \sin \alpha _{4}^{1} \end{array} \right) \\ \alpha _{4}^{1}= & {} \arccos \left( \frac{b {{}^2} +c {{}^2} -a {{}^2} }{2bc}\right) =\arccos \left( \frac{ (R_{2}+R_{1})^{2}+(R_{1}+R_{3})^{2}-(R_{3}+R_{2})^{2}}{ 2(R_{2}+R_{1})(R_{1}+R_{3})}\right) \\= & {} \arccos \left( \frac{R_{1}R_{2}+R_{1}R_{3}-R_{2}R_{3}+R_{1}^{2}}{ (R_{3}+R_{1})(R_{1}+R_{2})}\right) \quad . \end{aligned}$$

Exploiting

$$\begin{aligned} \cos \varphi _{4}^{1}:=\frac{(1,0)(\mathbf{x}_{3}-\mathbf{x}_{1})}{ \left\| \mathbf{x}_{3}-\mathbf{x}_{1}\right\| _{2}}=\frac{x_{32}-x_{12} }{R_{1}+R_{3}} \end{aligned}$$

we get

$$\begin{aligned} \mathbf{x}_{2}=\mathbf{x}_{1}+\left( \begin{array}{cc} \cos \varphi _{4}^{1} &{} \sin \varphi _{4}^{1} \\ -\sin \varphi _{4}^{1} &{} \cos \varphi _{4}^{1} \end{array} \right) \mathbf{x}_{2}^{\prime }=\mathbf{x}_{1}+\left( \begin{array}{cc} \cos \varphi _{4}^{1} &{} \sqrt{1-\cos ^{2}\varphi _{4}^{1}} \\ -\sqrt{1-\cos ^{2}\varphi _{4}^{1}} &{} \cos \varphi _{4}^{1} \end{array} \right) \mathbf{x}_{2}^{\prime }\quad . \end{aligned}$$

With known $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$, we apply the procedure of three circles again to the triangle obtained by the centers of circles 1, 2 and 4.

$$\begin{aligned} \alpha _{4}^{2}= & {} \arccos \left( \frac{ R_{1}R_{2}+R_{1}R_{4}-R_{2}R_{4}+R_{1}^{2}}{(R_{4}+R_{1})(R_{1}+R_{2})} \right) \\ \mathbf{x}_{4}^{\prime }= & {} (R_{1}+R_{4})\left( \begin{array}{c} \cos \alpha _{4}^{2} \\ \sin \alpha _{4}^{2} \end{array} \right) \quad . \end{aligned}$$

With

$$\begin{aligned} \cos \varphi _{4}^{2}:=\frac{(1,0)(\mathbf{x}_{2}-\mathbf{x}_{1})}{ \left\| \mathbf{x}_{2}-\mathbf{x}_{1}\right\| _{2}}=\frac{x_{22}-x_{12} }{R_{1}+R_{2}} \end{aligned}$$

we get

$$\begin{aligned} \mathbf{x}_{4}=\mathbf{x}_{1}+\left( \begin{array}{cc} \cos \varphi _{4}^{2} &{} \sin \varphi _{4}^{2} \\ -\sin \varphi _{4}^{2} &{} \cos \varphi _{4}^{2} \end{array} \right) \mathbf{x}_{4}^{\prime }=\mathbf{x}_{1}+\left( \begin{array}{cc} \cos \varphi _{4}^{2} &{} \sqrt{1-\cos ^{2}\varphi _{4}^{2}} \\ -\sqrt{1-\cos ^{2}\varphi _{4}^{2}} &{} \cos \varphi _{4}^{2} \end{array} \right) \mathbf{x}_{4}^{\prime }\quad . \end{aligned}$$

The formulae for four circles can also be derived, by applying the 3-circle formulae anti-clockwise to the circle tours 1-2-3, and then 1-3-4. Note that circles 1 and 3 in 1-3-4 are not computed but just fixed to the results obtained by 1-2-3. This idea can be extrapolated to n circles if circles $2\ldots n$ touch circle 1.

3.4 Congruent circles

If all circles have the same radius R, the length $\ell$ of $\partial {\mathcal {S}}$ is given by

$$\begin{aligned} \ell =\ell _{\mathrm {A}}+\ell _{\mathrm {L}}=2\pi R+\sum _{i_{1}*i_{2}}\ell _{i_{1}i_{2}}\quad , \end{aligned}$$

(3.21)

where $\ell _{i_{1}i_{2}}=d_{i_{1}i_{2}}$, if a line segment originates on circle $i_{1}$ and destinates on circle $i_{2}$ (this is indicated by the notation $i_{1}*i_{2}$; thus, the sum is only over all pairs of connected circles counted anti-clockwise) and where $d_{i_{1}i_{2}}$ denotes the distance between the centers of the circles. Note that this property $\ell _{i_{1}i_{2}}=d_{i_{1}i_{2}}$ also holds when the circles do not touch each other.

4 Numerical experiments

The monolith formulation (non-convex MINLP) as well as the polylithic approaches are implemented in GAMS 24.8.3. The computations are executed on a 64 bit machine with an Intel(R) Core(TM) i7 CPU 3.33 GHz, 16 GB RAM running Windows 7. The time limit is set to 24 hours. All numerical experiments in this section have been performed with $N_{i}^{\mathrm {ls}}=1$ , i.e., we allow for each circle at most one incoming and one outgoing line segment. We use the two global solvers BARON (with CPLEX for the LP relaxation and MINOS for the NLP problem) and LINDO using a single core processor. We have performed the followings sets of algorithmic experiments:

• 1. Monolith (M): The MINLP problem as it is. For examples containing up to five circles, we can close the gap $\Delta$ between the upper and lower bound and prove global optimality. We distinguish between the two settings

  • (a) Tour (MT): We fix the binary variables $\delta _{j}^{\mathrm {A}}$, $\delta _{ij}^{\mathrm {S}}$, $\delta _{ij}^{\mathrm {D}}$, and $\delta _{ij}$ to unity to enforce the specified tour. This eliminates most of the binary variables; essentially, it reduces the original MINLP problem to an NLP problem.

  • (b) No tour (MnT): No variable is fixed or bound a priori.

• 2. Polylithic 1 (P1): A polylithic approach which uses a homotopy approach. At first, we solve the circle packing problem minimizing the area or the perimeter of the rectangle hosting all circles. From these initial arrangement of circles, we derive initial values for the binary variables $\delta _{j}^{\mathrm {A}}$, $\delta _{ij}^{\mathrm {S}}$, $\delta _{ij}^{ \mathrm {D}}$, and $\delta _{ij}$ and follow up with the MinPerim model.

• 3. Polylithic 2 (P2): Similar to Polylithic 1, but we apply a local improvement heuristic by means of a 2-opt swap procedure in which the position of two circles are swapped. If the swap leads to improvement we keep the swap, else we select other two circles.

• 4. Complete enumeration: For instances with up to five circles, the complete sets of tours can be constructed. We solve the remaining NLP problems and pick the best solution.

We perform our computational tests on a set of two different instance types Cx or Dx. Instances with congruent circles start with the prefix “C” while instances with non congruent circles start with “D”. Parameter x stands for the number of circles considered in each instance, e.g., D03 represents an instance with three non congruent circles. If the final gap for minimizing is smaller than $10^{-4}$, the instance is labeled with an $^{*}$.

Congruent circles Table 1 shows the results for congruent circles of radius 0.5. For each instance, we minimize the lengths of the line segments only which is sufficient to minimize the perimeter according to Sect. 2.3.1 (see also Appendix B.3.1). For each instance we have tested all algorithmic settings, e.g., MnT or P1, described above. While in our computational pretests, we test each of the algorithmic settings described above, column “AS” reports the algorithmic settings leading to the best solution in terms of the objective function or obtained lower bound for each instance. The lower bounds obtained from the isoperimetric inequality (2.1) and the LP relaxation for the MINLP are given in columns “$z^{\mathrm {ie}}$” and “$z^{\mathrm {lp}}$ ”, respectively. The gap, $\Delta$, in $\%$ between the best solution obtained for total perimeter, $\ell =\ell _{\mathrm {L}}+\ell _{ \mathrm {A}}$ within the time limit and the best lower bound $\max \left\{ z^{ \mathrm {ie}},z^{\mathrm {lp}}\right\}$ is given in column “$\Delta$”, i.e., $\Delta =\frac{(\ell -\max \left\{ z^{\mathrm {ie}},z^{\mathrm {lp}}\right\} )}{\ell }$. The absolute length for the line segments, the arcs and the total perimeter obtained are shown in columns $\ell _{\mathrm {L}}$, $\ell _{\mathrm {A}}$ and $\ell$, respectively.

Table 1 Results for congruent circles in which the line segments are minimized

The results in Table 1 reveal that for instances containing up to 20 circles the lower bound obtained by the isoperimetric inequality (2.1) is better than the lower bound obtained from the LP relaxation for the MINLP. For instances with more than 20 circles, however, the MINLP’s lower bound becomes better and significantly outperforms the lower bound of the isoperimetric inequality (2.1) the more circles are considered. We also can see that the setting P1 leads to the best solution over all instances. Only for instance C06 the algorithmic setting MnT leads to the best result. The solution for the instance C85 with 85 congruent circles is shown in Fig. 6.

Fig. 6

Arrangements of circles for instance C85 with 85 congruent circles with radius 1 (the figure is turned $90^{\circ }$)

Non-congruent circles

As the consideration of the arcs in the model is computationally expensive, we compare the results to a model version with a relaxed objective function in which the sum of lengths of the line segments $\ell _{\mathrm {L}}$ is minimized only. The model formulation minimizing line segments only will be denoted as relaxed model formulation.

Table 2 shows the results with the objective function minimizing line segments and arcs, $\ell _{\mathrm {L}}+\ell _{ \mathrm {A}}$, while Table 3 depicts the results for minimizing $\ell _{\mathrm {L}}$ only. The columns have the similar meaning as in Table 1; note column $\Delta$ reports the gap in $\%$ between the obtained length of the perimeter, $\ell$, and the best lower bound found.

Table 2 Non-congruent circles minimizing line segments and arcs

For the non-relaxed model formulation algorithmic setting P1 leads in most of the instances to the best solution found (see Table ), which is similar to the observation for congruent circles. Only for the two instances DC03 to DC04 we reach gaps smaller than $10^{-4}$. In contrast, If we minimize line segments only, we reach this gap for instances with up to five circles (see Table 3). For the relaxed model formulation, the best algorithmic setting for instances with up to 8 circles was obtained with MT. For greater instances, algorithmic setting P1 becomes superior.

Table 3 Non-congruent circles minimizing line segments only

Further comparing the results of Table 2 and Table 3, we observe that the length of line segments as well as the length of the arcs differ for 7 out of 9 instances. For example, in instance DC10 the line segment length of the solution for the relaxed model is less than that for the non-relaxed model formulation, while in the non-relaxed solution the total arc length is less. For instance DC09 and instance DC28 the relaxed model even lead to a slightly smaller objective value than the non-relaxed one. Overall instances, both objective function values, for relaxed and non-relaxed, differ by 1% only on average.

4.1 Interesting findings

For congruent circles, we were expecting point-symmetric solutions. In contrast to our expected results, the minimal length configuration of C06 consists of five line segments displayed in Fig. 7, and not the symmetric and hexagonal triangle-shaped configuration consisting of three line segments.

Fig. 7

Solution representation of instance C06

C07 has a very symmetric optimal solution with one circle in the center surrounded by the other six contributing a 60$^{\circ }$ arc to $\partial {\mathcal {S}}$. The center coordinates, for general radius R, are given by

$$\begin{aligned} \mathbf{x}_{i}= & {} R(3,1+2(i-1)\quad ,\quad i=1,2,3 \\ \mathbf{x}_{4}= & {} R(3-\sqrt{3},1) \\ \mathbf{x}_{5}= & {} R(3-\sqrt{3},2) \\ \mathbf{x}_{6}= & {} R(3+\sqrt{3},1) \\ \mathbf{x}_{7}= & {} R(3+\sqrt{3},2)\quad . \end{aligned}$$

This configuration with six line segments of size 2R follows from the optimal configuration of C06 with five line segments by adding one circle in the free position of the optimal C06 configuration display in Fig. 7. The optimal length of C07 is $6+\pi \approx 9.1416.$ Note that the lower bound for seven identical circles of radius $R=0.5$ derived from the isoperimetric inequality (2.1) and Wegner inequality (page 109 in [4]) is 9.0033, i.e., a small gap of only 1.5%.

The optimal solution for C06 is

$$\begin{aligned} \mathbf{x}_{i}= & {} R(3,1+2(i-1)\quad ,\quad i=1,2 \\ \mathbf{x}_{3}= & {} R(3-\sqrt{3},1) \\ \mathbf{x}_{4}= & {} R(3-\sqrt{3},2) \\ \mathbf{x}_{5}= & {} R(3+\sqrt{3},1) \\ \mathbf{x}_{6}= & {} R(3+\sqrt{3},2) \end{aligned}$$

with optimal length $5.7321+\pi$$\approx 8.8736$ and the lower bound is 8.3267, i.e., a gap of 6.2%. The gap is larger as $\partial \mathcal { S}$ deviates more from a circle when compared to C07.

5 Conclusions

This paper studies the problem of arranging circles with possibly different radii in a plane such that the length $\ell$ of the boundary’s perimeter of the surrounding convex hull is minimized. To solve the problem, we have developed a non-convex MINLP model and provided interesting theoretical insights.

While we have shown by a counter example that it is generally not sufficient to minimize the line segments $\ell _{\mathrm {L}}$ only to obtain a configuration minimizing the total perimeter $\ell =\ell _{\mathrm {L}}+\ell _{\mathrm {A}}$, for instances considering congruent circles with equal radii only, it is sufficient. A still open question is whether there is also a counter example for the following conjecture: Minimal $\ell$ implies that $\ell _{\mathrm {L}}$ is minimal, i.e., minimal $\ell _{\mathrm {L}}$ is necessary for minimal $\ell$.

We exploited the isoperimetric inequality (2.1) to get a tighter lower bound for the perimeter than the lower bound obtained by the relaxation of the MINLP. As we could show in our numerical experiments, problem instances with only congruent circles are computational better tractable than non-congruent instances, as for congruent instances only the line segments have to be minimized. For small instances with up to five non-congruent circles, and minimizing only $\ell _{\mathrm {L}}$ the MINLP problems we obtained gaps smaller than $10^{-4}$ with the current state-of-the art global solvers BARON and LINDO available in GAMS. For larger problems of up to 90 circles, the relative gap between the upper and lower bound provided by the global solvers remains larger than 7 percent. The computational speed is enhanced if the line segments are only minimized. Although this leads to a relaxation of the original problem with a different circle configuration, the difference to the results obtained by minimizing line segments and arcs is small. The other advantage is that the gap can be closed at least in smaller problem instances.

Appendices

Notation

We start with the symbols introduced in the derivation of the model; they are not used in the MINLP model directly.

$\Delta$ :

the difference between the upper and lower bound from the LP relaxation for the MINLP provided by the solver.

$\partial {\mathcal {S}}$ :

the perimeter of the convex hull hosting all circles.

${\mathcal {H}}_{ij}$ :

hyperplane induced by the circular line segment of circle i connecting a pair of ingoing and outgoing vertices $\mathbf{v}_{j}^{\mathrm {la}}$ and $\mathbf{v}_{j++1}^{\mathrm {al}}$ located on that circle. In our 2D problem, ${\mathcal {H}}_{ij}$ is a straight line.

${\mathcal {H}}_{j}$ :

hyperplane induced by line segment j connecting and tangential to two adjacent circles. In our 2D problem, ${\mathcal {H}}_{j}$ is a straight line.

m :

the number of circles touching the convex hull; $m \le n$.

n :

the number of circles to be placed.

$N^\mathrm {ls}_i$ :

for circle i, the maximal number of incoming or outgoing line segments.

$\mathbf{n}_{j}^{\mathrm {H}}$ :

the normal vector onto hyperplane ${\mathcal {H}}_{j}$ induced by line segment j connecting two circles.

${\mathcal {S}}$ :

the convex hull hosting all circles.

$S_{ij}$ :

specifying whether arc on circle i induced by line segment j is a major ($S_{ij}=1$) or minor sector ($S_{ij}=0$); $S_{ij} \in \{0,1\}$.

$\mathbf{v}_{j}^{\mathrm {al}}$ :

vertex connecting a source arc to line segment j; $\mathbf{v}_{j}^{\mathrm {al}}=(v_{1j}^{\mathrm {al}},v_{2j}^{\mathrm {al}})$

$\mathbf{v}_{j}^{\mathrm {an}}$ :

vertex connecting a source arc line segment $j+1$; $\mathbf{v}_{j}^{\mathrm {an}}=(v_{1j}^{\mathrm {an}},v_{2j}^{\mathrm {an}})$.

$\mathbf{v}_{j}^{\mathrm {la}}$ :

vertex connecting line segment j to a destination arc; $\mathbf{v}_{j}^{\mathrm {la}}=(v_{1j}^{\mathrm {la}},v_{2j}^{\mathrm {la}})$.

$\mathbf {x}^{\mathrm {c}}$ :

radius-weighted center of all circles.

The symbols used in the MINLP model are summarized in the following subsections.

1.1 Indices and sets

• $d \in \{1,2\}$ index for the dimension; $d=1$ represents the length, and $d=2$ the width of the rectangle.

• $i\in {\mathcal {I}}:= \{ 1, \ldots , n \}$ objects (circles) to be packed.

• $j\in {\mathcal {J}}:= \{ 1, \ldots , m \le N^\mathrm {J} \le n \}$ line segments potentially connecting circles and tangential to the convex hull. Note that the number m of active line segments is identical to the number of circular arcs contributed to $\partial {\mathcal {S}}$.

1.2 Data

$E_d$ :

length ($d=1$) and width ($d=2$) of the rectangle.

L :

length of the rectangle.

$R_i$ :

radius of circle i to be packed.

$S_i$ :

indicator specifying to use a major ($S_i=1)$ or minor ($S_i=0)$ sector of circle i contributing an arc to the boundary of the convex hull.

W :

width of the rectangle.

1.3 Decision variables

$d_{j}^{\mathrm {H}}$ :

distance of hyperplane ${\mathcal {H}}_{j}$ induced by line segment j to the origin of the coordinate system.

$m_{ij}^{\mathrm {D}}$ :

distance of hyperplane ${\mathcal {H}}_{ij}$ induced by circle segment i to the origin of the coordinate system.

$\mathbf {m}_{dij}^{\mathrm {H}}$ :

a specific orthogonal vector onto the circle line segment of circle i connecting $\mathbf {v}_{j}^{\mathrm {la}}$ and $\mathbf {v}_{j}^{\mathrm {an}}$.

$n_{dj}^{\mathrm {H}}$ :

the normal vector onto hyperplane ${\mathcal {H}}_{j}$ induced by line segment j connecting two circles (direction d).

$x_{d}^{\mathrm {R}}$ :

(continuous) extension of the rectangle in dimension d.

$x_{id}^0$ :

(continuous) coordinates of the center vector of circle i to be packed.

$\alpha _{ij}$ :

(continuous) sector angle of circle i induced by line segment j.

$\delta _{ij}$ :

(binary) indicates whether circle i has incoming or outgoing line segment j.

$\delta _{j}^{\mathrm {A}}$ :

(binary) indicates whether vertices $\mathbf {v}_{j}^{\mathrm {al}}$ and $\mathbf {v}_{j}^{\mathrm {la}}$ are active, i.e., line segment j is used.

$\delta _{ij}^{\mathrm {D}}$ :

(binary) indicates whether circle i is the destination of line segment j.

$\delta _{j}^{\mathrm {L}}$ :

(binary) indicates whether line segment j is the last active one used.

$\delta _{ij}^{\mathrm {S}}$ :

(binary) indicates whether circle i is the origin of line segment j.

$\ell$ :

(continuous) length of the convex hull perimeter.

$\mu$ :

(integer) the number of active line segments.

Detailed derivations

In this section we provide various derivations in detail.

1.1 Segment and angle

For a given circle of radius R and angle $\alpha$, measured in radians, the length of the corresponding circular arc is given by

$$\begin{aligned} b=R\alpha \quad . \end{aligned}$$

The length s of a circular segment is related to angle $\alpha$ by

$$\begin{aligned} s=2R\sin \frac{\alpha }{2}\quad \Longleftrightarrow \quad \alpha =2\arcsin \frac{s}{2R}\quad , \end{aligned}$$

and thus

$$\begin{aligned} b=2R\arcsin \frac{s}{2R}\quad , \end{aligned}$$

where $s=\left\| \mathbf {m}_{ij}^{\mathrm {H}}\right\| _{2}$ if circle i contributes a circular arc induced by line segment j to the boundary of the convex hull. We have exploited this in (2.59).

Unfortunately, the strong global solver BARON available to us, does not support trigonometric functions. Therefore, we approximate the $\arcsin$ -function. We could approximate $\arcsin x$ by its Taylor series expansion

$$\begin{aligned} \arcsin x= & {} \sum _{n=0}^{\infty }\frac{(2n)!}{4^{n}(n!)^{2}(2n+1)}x^{2n+1} \\= & {} x+\frac{1}{6}x^{3}+\frac{3}{40}x^{5}+\frac{5}{112}x^{7}+\frac{ 35}{1152}x^{9}+\frac{63}{2816}x^{11}+O\left( x^{13}\right) \quad , \end{aligned}$$

but as convergence is very slow near $x=1$, we take a different approximation. For $x\in [0,1]$ we use

$$\begin{aligned} \arcsin x\approx \frac{\pi }{2}-\sqrt{-\frac{1}{c}\ln \left( 1+\frac{x-1}{e} \right) } \end{aligned}$$

with

$$\begin{aligned} c=\frac{4}{\pi ^{2}}\left[ 1-\ln (e-1)\right] \quad . \end{aligned}$$

This approximation is accurate up to 0.35%, and it is exact in $x=0$ and $x=1$. For the full range, $x\in [-1,1]$, we use

$$\begin{aligned} \arcsin x\approx sign(x)\left[ \frac{\pi }{2}-\sqrt{-\frac{1}{c}\ln \left( 1+ \frac{x-1}{e}\right) }\right] \quad . \end{aligned}$$

Note that BARON supports the logarithmic function $\ln$. Although the approximation is very good, after the computations using BARON, we use the solution as initial point to LINDOGLOBAL which supports arcsin.

1.2 Useful inequalities

We exploit Theorem 4.3.1 (Wegner inequality, page 109) in [4] to obtain a lower bound of the area of the convex hull enclosing n unit discs. If $D_{n}$ is the convex hull of n non-overlapping unit discs $(R=1)$ then

$$\begin{aligned} A(D_{n})\ge \sqrt{12}(n-1)+\left( 2-\sqrt{3}\right) \left\lceil \sqrt{12n-3}-3\right\rceil +\pi \quad . \end{aligned}$$

(B.83)

For $R=0.5$, divide both sides of (B.83) by 4. If we also use the reverse isoperimetric inequality

$$\begin{aligned} 4\pi A\le L^{2}\quad , \end{aligned}$$

we get a lower bound $L_{\mathrm {lb}}$ on L, the length of the boundary $\partial {\mathcal {S}}$ of the convex hull ${\mathcal {S}}$. For instance, for $n=14$ and $R=0.5$, we get

$$\begin{aligned} L_{\mathrm {lb}}=\sqrt{\pi \left[ \sqrt{12}(n-1)+\left( 2-\sqrt{3}\right) \left\lceil \sqrt{12n-3}-3\right\rceil +\pi \right] }\approx 12.64\quad . \end{aligned}$$

The best solution we found for $n=14$ is 13.6057, i.e., a gap of 7.6 percent.

On page 99 in [4] we find the somewhat weaker inequality

$$\begin{aligned} A(D_{n})\ge \sqrt{12}n\ \quad , \end{aligned}$$

which for $R=0.5$ gives a lower bound of $L_{\mathrm {lb}}\approx$12.34. The closer $\partial {\mathcal {S}}$ to a circle, the tighter these lower bounds become.

1.3 Proofs

1.3.1 The sum of the angles

Consider any set of circles with radii $R_{i}$ enclosed by its convex hull ${\mathcal {S}}$. Note that here we do not require the ${\mathcal {S}}$ is minimal in its area or length of the perimeter of its boundary $\partial {\mathcal {S}}$ , i.e., no restrictions on whether the circles are detached or touching each other. The sum of the angles $\alpha _{i}$ (Note: For simplicity, we consider here only the case of circles contributing at most one arc to $\partial {\mathcal {S}}$, which allows us to neglect the index j. The idea of the proof works likewise for considering several arcs contributed by the same circle.) of the circular sectors contributing an arc to $\partial {\mathcal {S}}$ equals to $360^{\circ }$. Proof: If circle i does not contribute an arc to $\partial {\mathcal {S}}$, we set $\alpha _{i}=0$ . Consider circles $i=1$ and $i=2$ with centers $x_{i}^{\mathrm {0}}$, a corresponding circular sector, $\mathcal {C}_{1}$, contributing an arc to $\partial {\mathcal {S}}$, the origin $\mathbf {v}_{1}^{\mathrm {al}}\in \mathcal {C }_{1}$ of the outgoing line segment connecting to its adjacent circular segment, $\mathcal {C}_{2}$, $\mathcal {C}_{2}$ itself, and the destination point $\mathbf {v}_{1}^{\mathrm {la}}$$\in \mathcal {C}_{2}$ of the line segment as displayed in Fig. 8a. Since $\mathbf {v}_{1}^{\mathrm {al}}$ and $\mathbf {v}_{1}^{\mathrm {la}}$ are touching points on $\mathcal {C}_{2}$ and $\mathcal {C}_{1}$, they are orthogonal on the connecting line segment and the vectors $\mathbf {v}_{1}^{ \mathrm {al}}-x_{2}^{\mathrm {0}}$ and $\mathbf {v}_{1}^{\mathrm {la}}-x_{1}^{ \mathrm {0}}$ are parallel. We now perform a parallel shift of $\mathcal {C} _{2}$ to $\mathcal {C}_{1}$ along the line segment (see Fig. b and scale-down the larger circle so that the radii become equal.

Fig. 8

Four circles $i=1$, $i=2$, $i=3$ and $i=4$ arranged in the plane where each arc has an angle of $90^{\circ }$ (a). The shift of circle $i=2$ to the position of circle $i=1$ (b). a Arrangement of four circles in the plane, b shift the position of circle $i=2$ to $i=1$, c re-scale circle $i=2$ to match the size of $i=1$

As the vectors $\mathbf {v}_{1}^{\mathrm {al}}-x_{2}^{\mathrm {0}}$ and $\mathbf {v}_{1}^{\mathrm {la}}-x_{1}^{\mathrm {0}}$ are parallel, $\mathcal {C} _{2}$ matches $\mathcal {C}_{1}$. After a parallel shift of the center of $\mathcal {C}_{2}$ it matches exactly the center of $\mathcal {C}_{1}$ if the smaller circle is increased so that both radii are identical. After scaling $\mathcal {C}_{2}$ to match radius $R_{1}$, the union circular sector $\mathcal {C}_{1}\cup \mathcal {C}_{2}$ has an angle of $\alpha _{1}+\alpha _{2}$. Note that neither the parallel shifts nor the scaling change the individual angles. If we apply this procedure now to $\mathcal {C}_{1}\cup \mathcal {C}_{2}$ and $\mathcal {C}_{3}$, we obtain $\mathcal {C}_{1}\cup \mathcal {C}_{2}\cup \mathcal {C}_{3}$ with $\alpha _{1}+\alpha _{2}+\alpha _{3}$. If we continue to apply this procedure to all circles whose sectors contribute an arc to $\partial {\mathcal {S}}$, we obtain a circle with radius $R=R_{1}$ and thus $\sum _{i}$$\alpha _{i}=360.$ (q.e.d.)

In other words, we reduce $\partial {\mathcal {S}}$ to its scaled arcs with line segments eliminated and thus finally obtaining a circle.

1.3.2 Limit on the number of incoming and outgoing line segments

The number $n_{i}^{\mathrm {ls}}$ of incoming or outgoing line segments is identical to the maximal number of arcs which circle i can contribute to $\partial {\mathcal {S}}$. If we have one circle only, $\partial {\mathcal {S}}$ is identical to the circumference of that single circle, and thus $N_{1}^{ \mathrm {ls}}=0$. In Figs. 1, 2 and 3, we observe $\max _{i}\{N_{i}^{\mathrm {ls} }\}=1$, and in the non-minimal configurations displayed in Figs. 10a and 11 we have circles with $N_{i}^{\mathrm {ls}}=2$ , i.e., $\max _{i}\{N_{i}^{\mathrm {ls} }\}=2$. To derive reasonable value for $N_{i}^{\mathrm {ls}}$ for minimal configurations, we consider two cases:

• 1. Unrestricted problem: $L=W=\infty$, i.e., the fit-the-rectangle inequalities (2.24) and (2.25) are relaxed.

• 2. Restricted problem: The fit-the-rectangle inequalities (2.24) and (2.25) can be become active and need to be considered, especially, if the circles are large when compared to the size of the rectangle.

Unrestricted problem

For three or more circles, there exist arrangements such that a circle contributes two arcs to the convex hull boundary $\partial {\mathcal {S}}$, and thus has two incoming and two outgoing line segments. In Fig. 9, for example, the circle in the middle contributes one arc in the Northern, and one on its Southern hemisphere to $\partial {\mathcal {S}}$. But we will show that these arrangements are not minimal regarding the length of $\partial {\mathcal {S}}$. The optimal property that each outer circle contributes exactly one arc to the convex hull boundary$\partial {\mathcal {S}}$ will be denoted as property P in the following. Property P also is equivalent to the property that each outer circle has exactly one incoming and one outgoing line segment, i.e., $N_{i}^{\mathrm {ls}}=1$ for all circles outer circles i.

Fig. 9

Configuration with two incoming and outgoing line segments for the large circle $i=2$

In the case of two circles, both circles are outer circles and P is obviously fulfilled. For three circles the minimum length of $\partial {\mathcal {S}}$ is given by cluster solution, (3.6)

$$\begin{aligned} \ell _{\mathrm {L}3}=2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{3}}+\sqrt{ R_{3}R_{1}}\right] \end{aligned}$$

with one incoming and outgoing line segment. Now consider a generalized sausage configuration (by this, we mean a configuration with circles lined-up along a straight line, or deviate only slightly from this virtual straight line) under the assumption that circle $i=2$ is the largest circles placed in the middle with circle $i=1$ on the left and circle $i=3$ on the right side. Note that we have an outgoing line segment from circle 2 to circle 1, and an incoming line segment from circle 1 to circle 2, and a similar situation for the pair of circles 2 and 3. The total length $\ell _{ \mathrm {L}3}^{\mathrm {sc}}$ of all line segments from the exact solutions ( 3.2) is

$$\begin{aligned} \ell _{\mathrm {L}3}^{\mathrm {sc}}= & {} 4\left[ \sqrt{R_{1}R_{2}}+\sqrt{ R_{2}R_{3}}\right] \\= & {} 2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{3}}\right] +2\left[ \sqrt{ R_{1}R_{2}}+\sqrt{R_{2}R_{3}}\right] \\\ge & {} 2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{3}}\right] +2\sqrt{R_{3}R_{1}} =\ell _{\mathrm {L}3}\quad . \end{aligned}$$

Fig. 10

In a we see a configuration with one circle contributing two arcs. For this configuration, property P does not hold—and it has a large convex hull. In b we see an improved configuration which has property P and somewhat smaller length of $\partial {\mathcal {S}}$. Finally, c has minimal length of $\partial {\mathcal {S}}$. a Far from minimal configuration, b improved configuration, c minimal configuration

To provide a motivation for property P for the general case with $n > 3$ circles, let $i^*$ be the circle contributing two arcs to $\partial S$. Due to the convexity property of $\partial S$ circle $i^*$ has to be larger than or to the surrounding circles sharing a line with circle $i^*$. Note, since we have four lines leaving circle $i^*$ the number of circles sharing a line segment with $i^*$ are at most four and at least two. W.l.o.g. assume that one circle sharing a line segment with circle $i^*$ is placed on circle $i^*$ ’s left, denoted by $i^\text {left}$, and all other circles on its right side. For example, Fig. 10a shows a configuration in which the largest circle $i^* = 2$ contributes two arcs and circle $i^\text {left} = 1$ is placed on its left side. According to the conjecture in Section 5, minimal $\ell$ implies minimal $\ell _{\mathrm {L}}$. Thus, assuming the conjecture is true, the configuration with one circle on the left site and the all other circles on the right side cannot lead to minimal value of $\ell$ for the following reason: By moving circle $i^\text {left}$ from the left site to the right side of circle $i^*$, we reduce the number of required line segments by one and the total length $\ell _{\mathrm {L}}$ of all line segments. The last statement is true due to the following proposition

Proposition 1

Given two circles. The smaller the radii of one of two circles, the smaller the length of the line segment required to connect both circles with each other.

Proposition 1 is true as the length of the line segment between two circles depends on their radii (see Section 2.9.2). Thus, circle $i^{\text {left}}$ can be connected with any of the other circles on the right side of circle $i^{*}$ with a line segment having a length smaller or equal to the length of the previous line segment which connected circle $i^{*}$ with $i^{\text {left}}$. If we move the smallest circle $i=1$ in Fig. 10a to the right position as shown in Fig. 10b, $i=2$ contributes one arc only to $\partial {\mathcal {S}}$. The total number of required line segments is reduced by one and the total length $\ell$ of $\partial {\mathcal {S}}$ as well as the length of the line segments and arcs become smaller. If we now move circle 1 to the lower position as shown in Fig. 10c, we obtain the configuration with minimal value of $\ell$.

For the four-circle case with $R_{2}>R_{3}=R_{4}>R_{1}$ displayed in Fig. 10, we can explicitly prove that the sum $\ell _{\mathrm {L}}^{(\mathrm {a})}$ of line segment lengths of $\partial \mathcal {S }$ in configuration (a) is not minimal. According to (3.1), if we proceed counter-clockwise to consider the line segments of $\partial {\mathcal {S}}$, we obtain

$$\begin{aligned} \ell _{\mathrm {L}}^{(\mathrm {a})}= & {} 2\left[ \sqrt{R_{1}R_{2}}+\sqrt{ R_{2}R_{4}}+\sqrt{R_{4}R_{3}}+\sqrt{R_{3}R_{2}}+\sqrt{R_{2}R_{1}}\right] \\&2\left[ \sqrt{R_{1}R_{2}}+\sqrt{R_{2}R_{4}}+\sqrt{R_{3}R_{4}}+\sqrt{ R_{2}R_{3}}+\sqrt{R_{1}R_{2}}\right] \quad . \end{aligned}$$

Now we compare $\ell _{\mathrm {L}}^{(\mathrm {a})}$ to the minimal length $\ell _{\mathrm {L}4}=\min \left\{ \ell _{\mathrm {L}4}^{(1)},\ell _{\mathrm {L} 4}^{(2)},\ell _{\mathrm {L}4}^{(3)}\right\}$ of four circles given by one of the tours with lengths $\ell _{\mathrm {L}4}^{(1)},\ell _{\mathrm {L}4}^{(2)}$ and $\ell _{\mathrm {L}4}^{(3)}$ calculated by (3.18), (3.19) and (3.20). Exploiting $R_{2}>R_{3}=R_{4}$, we obtain

$$\begin{aligned} \ell _{\mathrm {L}}^{(\mathrm {a})}= & {} \ell _{\mathrm {L}4}^{(1)}+2\left[ \sqrt{ R_{1}}\left( \sqrt{R_{2}}-\sqrt{R_{4}}\right) \right]>\ell _{\mathrm {L} 4}^{(1)}\quad ,\\ \ell _{\mathrm {L}}^{(\mathrm {a})}= & {} \ell _{\mathrm {L}4}^{(2)}+2\left[ \sqrt{ R_{1}}\left( \sqrt{R_{2}}-\sqrt{R_{3}}\right) \right] >\ell _{\mathrm {L} 4}^{(2)}\quad , \end{aligned}$$

and

$$\begin{aligned} \ell _{\mathrm {L}}^{(\mathrm {a})}=\ell _{\mathrm {L}4}^{(3)}+2\left[ \sqrt{ R_{1}}\left( \sqrt{R_{2}}-\sqrt{R_{3}}\right) +\sqrt{R_{1}}\left( \sqrt{R_{2} }-\sqrt{R_{4}}\right) \right] >\ell _{\mathrm {L}4}^{(3)}\quad , \end{aligned}$$

i.e., $\ell _{\mathrm {L}}^{(\mathrm {a})}>\ell _{\mathrm {L}4}$.

Restricted case The fit-the-rectangle inequalities (2.24) and (2.25) can force the minimal length convex hull into generalized sausage configurations. This is illustrated by Fig. 11. Three circles with radii $R_{1}=R_{2}=2$ and $R_{3}=1.5$ have to be placed in a rectangle specified by $L=12$ and $W=4$. The minimal length $\ell _{*}=\ell _{\mathrm {L}}+\ell _{\mathrm {A}}$ is given by

$$\begin{aligned} \ell _{\mathrm {L}}=2\left[ 2R_{2}+2\sqrt{R_{2}R_{3}}\right] =8+4\sqrt{3} \approx 14.\,9282 \end{aligned}$$

and

$$\begin{aligned} \ell _{\mathrm {A}}= & {} \pi R_{1}+R_{2}\left[ 2\arccos \frac{2\sqrt{R_{2}R_{3}} }{R_{2}+R_{3}}\right] +R_{3}\left[ \pi -2\arccos \frac{2\sqrt{R_{2}R_{3}}}{ R_{2}+R_{3}}\right] \\= & {} \frac{7}{2}\pi +\arccos \frac{2\sqrt{R_{2}R_{3}}}{R_{2}+R_{3}}=\frac{7}{2} \pi +\arccos \frac{4\sqrt{3}}{7}\approx 11.1389 \end{aligned}$$

leading to an approximate value of $\ell _{*}\approx 26.0671$ realized by the center coordinates $\mathbf {x}_{1}^{\mathrm {0}}=(2,2)$, $\mathbf {x} _{2}^{\mathrm {0}}=(6,2)$ and $\mathbf {x}_{3}^{\mathrm {0}}=(9.5,2)$. In this example, that circle 2 has two incoming and outgoing line segments.

Fig. 11

Three circles with radii $R_{1}=R_{2}=2$ and $R_{3}=1.5$ have to be placed in a rectangle specified by $L=12$ and $W=4$. a shows the configuration for the minimal length ($\ell \approx 26.0671$), if two arcs per circle are allowed. Note that circle 2 contributes two tiny arcs ($\alpha _2 \approx 8.2132^{\circ }$). In b we allow one arc only resulting in length ($\ell \approx 27.5486$). a$N^{\mathrm {ls}}_i=2, \forall i$, b$N^{\mathrm {ls}}_i=1, \forall i$.

As expected, when computing a solution with one incoming and one outgoing line segment, we obtain the configuration as displayed in Fig. 11b with $\ell \approx 27.5486>\ell _{*}$. Therefore, for the restricted case, $N_{i}^{\mathrm {ls}}=1$ is too tight and we may lose the optimal solution. $N_{i}^{\mathrm {ls}}=2$ would be sufficient for this case.

Let us now consider a large circle with radius R and four small circles with radius r which touch the square ($L=W=2R$) on two adjacent sides of the square. From the condition

$$\begin{aligned} R+\frac{\sqrt{2}}{2}(R+r)+r=2R \end{aligned}$$

we derive

$$\begin{aligned} r=\frac{2-\sqrt{2}}{2+\sqrt{2}}R=\left( 3-2\sqrt{2}\right) R\approx 0.17157\cdot R\quad . \end{aligned}$$

This configuration has no degrees of freedom. All circles just fit into the square if we place the small circles into the corners of the square just touching the large circle. The large circle is not even an outer circle as the four line segments connecting the small circles are parts of the side of the rectangle. Only the small circles contribute arcs with equal angles

$$\begin{aligned} \alpha _{i}=\frac{\pi }{2}\quad ,\quad i\in {\mathcal {I}}_{\mathrm {s} }=\{2,3,4,5\} \end{aligned}$$

or $90^{\circ }$; therefore, we do not mention index j in this context.

Fig. 12

Minimal length configuration of five outer circles. The large circle with radius $R=1$ contributes four equal arcs to $\partial {\mathcal {S}}$, each with a small angle of $5.135^{\circ }$. Each small circle with radius $r=0.15$ adds one arc of $84.\,685^{\circ }$. The thin blue lines indicate show the rectangle, a square in this case. (Color figure online)

If we now slightly decrease the small circles to radius $r=0.15$, we obtain the minimal configuration with eight line segments as displayed in Fig. 12. All circles are outer circles, but now the large circle contributes four small arcs of angle $5.135^{\circ }$ to $\partial {\mathcal {S}}$, and thus has four outgoing and four ingoing line segments. Due to the symmetry, the small circles contribute arcs with equal angles

$$\begin{aligned} \alpha _{i}=\pi -2\arccos \frac{2\sqrt{0.15}}{1.15}\approx 1.\,478\quad ,\quad i\in {\mathcal {I}}_{\mathrm {s}}=\{2,3,4,5\} \end{aligned}$$

or $84.\,685^{\circ }$; again we neglect index j in this context. Thus, in this case we have $N_{1}^{\mathrm {ls}}=4$ and $N_{i}^{ \mathrm {ls}}=1$ for $i\in {\mathcal {I}}_{\mathrm {s}}$, as the arcs contributed by the large circle touch all four sides of the rectangle. Therefore, in the restricted case, it is worthwhile to think about the appropriate values for $N_{i}^{\mathrm {ls}}\in \{0,1,2,3,4\}$. If the circles are small compared to the size of the rectangle, $N_{i}^{\mathrm {ls}}=1$ works fine.