Circle packing in a square

Last updated

Circle packing in a square is a packing problem in recreational mathematics, where the aim is to pack n unit circles into the smallest possible square. Equivalently, the problem is to arrange n points in a unit square aiming to get the greatest minimal separation, dn, between points. [1] To convert between these two formulations of the problem, the square side for unit circles will be L = 2 + 2/dn.

Contents

Solutions

Solutions (not necessarily optimal) have been computed for every N ≤ 10,000. [2] Solutions up to N = 20 are shown below. [2] The obvious square packing is optimal for 1, 4, 9, 16, 25, and 36 circles (the six smallest square numbers), but ceases to be optimal for larger squares from 49 onwards. [2]

Number of circles (n)Square side length (L)dn [1] Number density (n/L2)Figure
120.25
2
≈ 3.414...

≈ 1.414...
0.172... 2 circles in a square.svg
3
≈ 3.931...

≈ 1.035...
0.194... 3 circles in a square.svg
4410.25 4 circles in a square.svg
5
≈ 4.828...

≈ 0.707...
0.215... 5 circles in a square.svg
6
≈ 5.328...

≈ 0.601...
0.211... 6 circles in a square.svg
7
≈ 5.732...

≈ 0.536...
0.213... 7 circles in a square.svg
8
≈ 5.863...

≈ 0.518...
0.233... 8 circles in a square.svg
960.50.25 9 circles in a square.svg
106.747...0.421... OEIS:  A281065 0.220... 10 circles in a square.svg
11
≈ 7.022...
0.398...0.223... 11 circles in a square.svg
12
≈ 7.144...

≈ 0.389...
0.235... 12 circles in a square.svg
137.463...0.366...0.233... 13 circles in a square.svg
14
≈ 7.732...

≈ 0.349...
0.226... 14 circles in a square.svg
15
≈ 7.863...

≈ 0.341...
0.243... 15 circles in a square.svg
1680.333...0.25 16 circles in a square.svg
178.532...0.306...0.234... 17 circles in a square.svg
18
≈ 8.656...

≈ 0.300...
0.240... 18 circles in a square.svg
198.907...0.290...0.240... 19 circles in a square.svg
20
≈ 8.978...

≈ 0.287...
0.248... 20 circles in a square.svg

Circle packing in a rectangle

Dense packings of circles in non-square rectangles have also been the subject of investigations. [3] [4]

See also

Related Research Articles

<span class="mw-page-title-main">Squaring the square</span> Mathematical problem

Squaring the square is the problem of tiling an integral square using only other integral squares. The name was coined in a humorous analogy with squaring the circle. Squaring the square is an easy task unless additional conditions are set. The most studied restriction is that the squaring be perfect, meaning the sizes of the smaller squares are all different. A related problem is squaring the plane, which can be done even with the restriction that each natural number occurs exactly once as a size of a square in the tiling. The order of a squared square is its number of constituent squares.

<span class="mw-page-title-main">Packing problems</span> Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, splitting a network prefix into multiple subnets, and technology mapping in FPGA semiconductor chip design.

<span class="mw-page-title-main">Sphere packing</span> Geometrical structure

In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.

In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function is equivalent to the minimization of the function .

<span class="mw-page-title-main">Heilbronn triangle problem</span> On point sets with no small-area triangles

In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

<span class="mw-page-title-main">Guillotine cutting</span> Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine.

The objective of the Thomson problem is to determine the minimum electrostatic potential energy configuration of N electrons constrained to the surface of a unit sphere that repel each other with a force given by Coulomb's law. The physicist J. J. Thomson posed the problem in 1904 after proposing an atomic model, later called the plum pudding model, based on his knowledge of the existence of negatively charged electrons within neutrally-charged atoms.

<span class="mw-page-title-main">Circle packing</span> Field of geometry closely arranging circles on a plane

In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap. The associated packing density, η, of an arrangement is the proportion of the surface covered by the circles. Generalisations can be made to higher dimensions – this is called sphere packing, which usually deals only with identical spheres.

<span class="mw-page-title-main">Tammes problem</span> Circle packing problem

In geometry, the Tammes problem is a problem in packing a given number of points on the surface of a sphere such that the minimum distance between points is maximized. It is named after the Dutch botanist Pieter Merkus Lambertus Tammes who posed the problem in his 1930 doctoral dissertation on the distribution of pores on pollen grains.

Circle packing in a circle is a two-dimensional packing problem with the objective of packing unit circles into the smallest possible larger circle.

Square packing is a packing problem where the objective is to determine how many congruent squares can be packed into some larger shape, often a square or circle.

Circle packing in an equilateral triangle is a packing problem in discrete mathematics where the objective is to pack n unit circles into the smallest possible equilateral triangle. Optimal solutions are known for n < 13 and for any triangular number of circles, and conjectures are available for n < 28.

<span class="mw-page-title-main">Circle packing in an isosceles right triangle</span> Two-dimensional packing problem

Circle packing in a right isosceles triangle is a packing problem where the objective is to pack n unit circles into the smallest possible isosceles right triangle.

A geometric separator is a line that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset is small.

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

Rectangle packing is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.

References

  1. 1 2 Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. New York: Springer-Verlag. pp.  108–110. ISBN   0-387-97506-3.
  2. 1 2 3 Eckard Specht (20 May 2010). "The best known packings of equal circles in a square" . Retrieved 25 May 2010.
  3. Lubachevsky, Boris D.; Graham, Ronald L. (2009). "Minimum perimeter rectangles that enclose congruent non-overlapping circles". Discrete Mathematics. 309 (8). Elsevier BV: 1947–1962. arXiv: math/0412443 . doi: 10.1016/j.disc.2008.03.017 . ISSN   0012-365X. S2CID   783236.
  4. Specht, E. (2013). "High density packings of equal circles in rectangles with variable aspect ratio". Computers & Operations Research. 40 (1). Elsevier BV: 58–69. doi:10.1016/j.cor.2012.05.011. ISSN   0305-0548.