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

DOI10.1007/S00454-022-00425-5arXiv2102.01537OpenAlexW3126202923WikidataQ114229286 ScholiaQ114229286MaRDI QIDQ6156095FDOQ6156095

Authors: Paolo Amore, Tenoch Morales 

Publication date: 12 June 2023

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

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.

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)