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!
cited_by cdi_FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3
cites cdi_FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3
container_end_page 267
container_issue 1
container_start_page 249
container_title Discrete & computational geometry
container_volume 70
creator Amore, Paolo
Morales, Tenoch
description 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.
doi_str_mv 10.1007/s00454-022-00425-5
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2822883086</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2822883086</sourcerecordid><originalsourceid>FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3</originalsourceid><addsrcrecordid>eNp9kE1Lw0AQhhdRsFb_gKcFz9H93u2xxKqFQgX1vGyS2TS1Tdrd5OC_d2sEb8LAzMDzzsCD0C0l95QQ_RAJEVJkhLEsTUxm8gxNqOBpFUKcowmhepZJrtUluopxSxI1I2aC1gvvm7KBtsfzXd2Fpt_sI_ZdwP0G8CO0EfCrKz-btsadx3nX1mE40XkTyh1EvGxjUwF2-O04uADX6MK7XYSb3z5FH0-L9_wlW62fl_l8lZWczvqsEMzoSgpNaSEUdx6kAKedroDrQhXAuFNOpjLGc6EVqKqiThtlSKFpxafobrx7CN1xgNjbbTeENr20zDBmDCdGJYqNVBm6GAN4ewjN3oUvS4k9ibOjOJvE2R9xVqYQH0MxwW0N4e_0P6lvfxRvkQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2822883086</pqid></control><display><type>article</type><title>Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square</title><source>Springer Nature</source><creator>Amore, Paolo ; Morales, Tenoch</creator><creatorcontrib>Amore, Paolo ; Morales, Tenoch</creatorcontrib><description>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.</description><identifier>ISSN: 0179-5376</identifier><identifier>EISSN: 1432-0444</identifier><identifier>DOI: 10.1007/s00454-022-00425-5</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Algorithms ; Combinatorics ; Computational Mathematics and Numerical Analysis ; Configurations ; Euclidean space ; Geometry ; Mathematics ; Mathematics and Statistics ; Packing density</subject><ispartof>Discrete &amp; computational geometry, 2023-07, Vol.70 (1), p.249-267</ispartof><rights>The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2022. Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3</citedby><cites>FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3</cites><orcidid>0000-0002-1321-9437</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Amore, Paolo</creatorcontrib><creatorcontrib>Morales, Tenoch</creatorcontrib><title>Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square</title><title>Discrete &amp; computational geometry</title><addtitle>Discrete Comput Geom</addtitle><description>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.</description><subject>Algorithms</subject><subject>Combinatorics</subject><subject>Computational Mathematics and Numerical Analysis</subject><subject>Configurations</subject><subject>Euclidean space</subject><subject>Geometry</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Packing density</subject><issn>0179-5376</issn><issn>1432-0444</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2023</creationdate><recordtype>article</recordtype><recordid>eNp9kE1Lw0AQhhdRsFb_gKcFz9H93u2xxKqFQgX1vGyS2TS1Tdrd5OC_d2sEb8LAzMDzzsCD0C0l95QQ_RAJEVJkhLEsTUxm8gxNqOBpFUKcowmhepZJrtUluopxSxI1I2aC1gvvm7KBtsfzXd2Fpt_sI_ZdwP0G8CO0EfCrKz-btsadx3nX1mE40XkTyh1EvGxjUwF2-O04uADX6MK7XYSb3z5FH0-L9_wlW62fl_l8lZWczvqsEMzoSgpNaSEUdx6kAKedroDrQhXAuFNOpjLGc6EVqKqiThtlSKFpxafobrx7CN1xgNjbbTeENr20zDBmDCdGJYqNVBm6GAN4ewjN3oUvS4k9ibOjOJvE2R9xVqYQH0MxwW0N4e_0P6lvfxRvkQ</recordid><startdate>20230701</startdate><enddate>20230701</enddate><creator>Amore, Paolo</creator><creator>Morales, Tenoch</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7XB</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>KR7</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M2O</scope><scope>M2P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PADUT</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0002-1321-9437</orcidid></search><sort><creationdate>20230701</creationdate><title>Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square</title><author>Amore, Paolo ; Morales, Tenoch</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2023</creationdate><topic>Algorithms</topic><topic>Combinatorics</topic><topic>Computational Mathematics and Numerical Analysis</topic><topic>Configurations</topic><topic>Euclidean space</topic><topic>Geometry</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Packing density</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Amore, Paolo</creatorcontrib><creatorcontrib>Morales, Tenoch</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Civil Engineering Abstracts</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>ProQuest Research Library</collection><collection>ProQuest Science Journals</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Research Library China</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><jtitle>Discrete &amp; computational geometry</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Amore, Paolo</au><au>Morales, Tenoch</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square</atitle><jtitle>Discrete &amp; computational geometry</jtitle><stitle>Discrete Comput Geom</stitle><date>2023-07-01</date><risdate>2023</risdate><volume>70</volume><issue>1</issue><spage>249</spage><epage>267</epage><pages>249-267</pages><issn>0179-5376</issn><eissn>1432-0444</eissn><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.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s00454-022-00425-5</doi><tpages>19</tpages><orcidid>https://orcid.org/0000-0002-1321-9437</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0179-5376
ispartof Discrete & computational geometry, 2023-07, Vol.70 (1), p.249-267
issn 0179-5376
1432-0444
language eng
recordid cdi_proquest_journals_2822883086
source Springer Nature
subjects Algorithms
Combinatorics
Computational Mathematics and Numerical Analysis
Configurations
Euclidean space
Geometry
Mathematics
Mathematics and Statistics
Packing density
title Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T04%3A18%3A35IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Efficient%20Algorithms%20for%20the%20Dense%20Packing%20of%20Congruent%20Circles%20Inside%20a%20Square&rft.jtitle=Discrete%20&%20computational%20geometry&rft.au=Amore,%20Paolo&rft.date=2023-07-01&rft.volume=70&rft.issue=1&rft.spage=249&rft.epage=267&rft.pages=249-267&rft.issn=0179-5376&rft.eissn=1432-0444&rft_id=info:doi/10.1007/s00454-022-00425-5&rft_dat=%3Cproquest_cross%3E2822883086%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c319t-b4287d54711b463afe54ea7a7de37b6be23a6a56a588f3476e6dd1a78680b71d3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2822883086&rft_id=info:pmid/&rfr_iscdi=true