Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio

In this paper we consider the problem of packing a fixed number of identical circles inside the unit circle container, where the packing is complicated by the presence of fixed size circular prohibited areas. Here the objective is to maximise the radius of the identical circles. We present a heuristic for the problem based upon formulation space search. Computational results are given for six test problems involving the packing of up to 100 circles. One test problem has a sin...

Packings of regular convex polygons ($n$-gons) that are sufficiently dense have been studied extensively in the context of modeling physical and biological systems as well as discrete and computational geometry. Former results were mainly regarding densest lattice or double-lattice configurations. Here we consider all two-dimensional crystallographic symmetry groups (plane groups) by restricting the configuration space of the general packing problem of congruent copies of a c...

A compact circle-packing $P$ of the Euclidean plane is a set of circles which bound mutually disjoint open discs with the property that, for every circle $S\in P$, there exists a maximal indexed set $\{A_{0},\ldots,A_{n-1}\}\subseteq P$ so that, for every $i\in\{0,\ldots,n-1\}$, the circle $A_{i}$ is tangent to both circles $S$ and $A_{i+1\mod n}.$ We show that there exist at most $13617$ pairs $(r,s)$ with $0<s<r<1$ for which there exist a compact circle-packing of the pla...

We consider the problem of finding all enclosing rectangles of minimum area that can contain a given set of rectangles without overlap. Our rectangle packer chooses the x-coordinates of all the rectangles before any of the y-coordinates. We then transform the problem into a perfect-packing problem with no empty space by adding additional rectangles. To determine the y-coordinates, we branch on the different rectangles that can be placed in each empty position. Our packer allo...

A packing of disks in the plane is a set of disks with disjoint interiors. This paper is a survey of some open questions about such packings. It is organized into five themes: compacity, conjugacy, density, uniformity and computability.

Suppose one has a collection of disks of various sizes with disjoint interiors, a packing in the plane, and suppose the ratio of the smallest radius divided by the largest radius lies between $1$ and $q$. In his 1964 book Regular Figures (MR0165423), L\'aszl\'o Fejes T\'oth found a series of packings that were his best guess for the maximum density for any $1 > q > 0.2$. Meanwhile Gerd Blind in (MR0275291, MR0377702) proved that for $1 \ge q > 0.72$, the most dense packing po...

Consider the problem of fnding the smallest area convex $k$-gon containing $n\in\mathbb{N}$ congruent disks without an overlap. By using Wegner inequality in sphere packing theory we give a lower bound for the area of such polygons. For several cases where this bound is tight we construct corresponding optimal polygons. We also discuss its solution for some cases where this bound is not tight, e.g. $n = 2$ and $k$ is odd, and $n = 3$; $k = 4$. On the way to prove our results ...

This paper determines the optimal upper bound for the simultaneous packing and covering constants of the two-dimensional centrally symmetric convex domains. It solved a problem opening for more than thirty years.

We consider circle packings in the plane with circles of sizes $1$, $r\simeq 0.834$ and $s\simeq 0.651$. These sizes are algebraic numbers which allow a compact packing, that is, a packing in which each hole is formed by three mutually tangent circles. Compact packings are believed to maximize the density when there are possible. We prove that it is indeed the case for these sizes. The proof should be generalizable to other sizes which allow compact packings and is a first st...

Based on numerical simulations that we have carried out, we provide evidence that for regular polygons with $\sigma= 6j$ sides (with $j=2,3,\dots$), $N(k)=3 k (k+1)+1$ (with $k=1,2,\dots$) congruent disks of appropriate size can be nicely packed inside these polygons in highly symmetrical configurations which apparently have maximal density for $N$ sufficiently small. These configurations are invariant under rotations of $\pi/3$ and are closely related to the configurations w...