Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square

We study dense packings of a large number of congruent non-overlapping circles inside a square by looking for configurations which maximize the packing density, defined as the ratio between the area occupied by the disks and the area of the square container. The search for these configurations is ca...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2023-07, Vol.70 (1), p.249-267
Main Authors: Amore, Paolo, Morales, Tenoch
Format: Article
Language:English
Subjects:
Algorithms
Combinatorics
Computational Mathematics and Numerical Analysis
Configurations
Euclidean space
Geometry
Mathematics
Mathematics and Statistics
Packing density
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study dense packings of a large number of congruent non-overlapping circles inside a square by looking for configurations which maximize the packing density, defined as the ratio between the area occupied by the disks and the area of the square container. The search for these configurations is carried out with the help of two algorithms that we have devised: a first algorithm is in charge of obtaining sufficiently dense configurations starting from a random guess, while a second algorithm improves the configurations obtained in the first stage. The algorithms can be used sequentially or independently. The performance of these algorithms is assessed by carrying out numerical tests for configurations with a large number of circles.
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-022-00425-5