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

In the classic circle packing problem, one asks whether a given set of circles can be packed into a given container. Packing problems like this have been shown to be $\mathsf{NP}$-hard. In this paper, we present new sufficient conditions for packing circles into square and triangular containers, using only the sum of the circles' areas: For square containers, it is possible to pack any set of circles with a combined area of up to approximately 53.90% of the square's area. And...

We describe an algorithm that allows one to find dense packing configurations of a number of congruent disks in arbitrary domains in two or more dimensions. We have applied it to a large class of two dimensional domains such as rectangles, ellipses, crosses, multiply connected domains and even to the cardioid. For many of the cases that we have studied no previous result was available. The fundamental idea in our approach is the introduction of "image" disks, which allows one...

We consider the online problem of packing circles into a square container. A sequence of circles has to be packed one at a time, without knowledge of the following incoming circles and without moving previously packed circles. We present an algorithm that packs any online sequence of circles with a combined area not larger than 0.350389 0.350389 of the square's area, improving the previous best value of {\pi}/10 \approx 0.31416; even in an offline setting, there is an upper b...

The article presents the mathematical sequences describing circle packing densities in four different geometric configurations involving a hexagonal lattice based equal circle packing in the Euclidian plane. The calculated sequences take form of either polynomials or rational functions. If the circle packing area is limited with a circle, the packing densities tend to decrease with increasing number of the packed circles and converge to values lower than {\pi}/(2\sqrt{3}). In...

We show that deciding whether a given set of circles can be packed into a rectangle, an equilateral triangle, or a unit square are NP-hard problems, settling the complexity of these natural packing problems. On the positive side, we show that any set of circles of total area 1 can be packed into a square of size 4/\sqrt{pi}=2.2567... These results are motivated by problems arising in the context of origami design.

This paper addresses the equal circle packing problem, and proposes an efficient Quasi-physical Quasi-human (QPQH) algorithm. QPQH is based on a modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm which we call the local BFGS and a new basin hopping strategy based on a Chinese idiom: alternate tension with relaxation. Starting from a random initial layout, we apply the local BFGS algorithm to reach a local minimum layout. The local BFGS algorithm fully utilizes the nei...

Previously published packings of equal disks in an equilateral triangle have dealt with up to 21 disks. We use a new discrete-event simulation algorithm to produce packings for up to 34 disks. For each n in the range 22 =< n =< 34 we present what we believe to be the densest possible packing of n equal disks in an equilateral triangle. For these n we also list the second, often the third and sometimes the fourth best packings among those that we found. In each case, the struc...

Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations.

We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $\delta=\frac{8}{5\pi}\approx 0.509$. This implies that any set of (not necessarily equal) squares of total area $A \leq \frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $\varepsilon>0$ there are sets of squares of total area $\frac{8}{5}+\varepsilon$ that cannot be packed, even if s...

We are interested in the following problem of covering the plane by a sequence of congruent circular disks with a constraint on the distance between consecutive disks. Let $(\mathcal{D}_n)_{n \in \mathbb N}$ be a sequence of closed unit circular disks such that $\cup_{n \in \mathbb{N}} \mathcal{D}_n = \mathbb {R}^2$ with the condition that for $n \ge 2$, the center of the disk $\mathcal{D}_n$ lies in $\mathcal{D}_{n-1}$. What is a "most economical" or an optimal way of placin...