Efficient algorithms for the dense packing of congruent circles inside a square

DOI10.1007/S00454-022-00425-5MaRDI QIDQ6156095zbMATH OpenOpenAlexWikidataFDO

Authors Paolo Amore, Tenoch Morales

Publication date 12 June 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.01537

zbMATH Keywords

optimizationcircle packing

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical approximation and computational geometry (primarily algorithms) (65Dxx)

Abstract: 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.

Cites work

• scientific article; zbMATH DE number 432979 (Why is no real title available?)
• A literature review on circle and sphere packing problems: models and methodologies
• A proof of the Kepler conjecture
• Improved interval methods for solving circle packing problems in the unit square
• Many-particle jumps algorithm and Thomson's problem
• New approaches to circle packing in a square. With program codes.
• On a Geometric Extremum Problem
• Packing up to 50 equal circles in a square
• The Densest Packing of 9 Circles in a Square
• The pursuit of perfect packing
• Über die dichteste Kugellagerung

Cited in

(5)

• scientific article; zbMATH DE number 1629820 (Why is no real title available?)
• New approaches to circle packing in a square. With program codes.
• A memetic algorithm to pack unequal circles into a square
• Greedy algorithms for packing unequal circles into a rectangular container
• scientific article; zbMATH DE number 5629935 (Why is no real title available?)

This page was built for publication: Efficient algorithms for the dense packing of congruent circles inside a square

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6156095)