News & Analysis
/
Article

Algorithms optimize circle packing in regular polygons

FEB 24, 2023
The complex geometrical problem of packing has applications in charge distribution and granular matter.
Algorithms optimize circle packing in regular polygons internal name

Algorithms optimize circle packing in regular polygons lead image

Social distancing exemplifies the geometric problem of packing by determining how many people, separated by a given distance, can fit within a space. In a circle packing problem, the goal is to maximize the packing fraction: the ratio of space covered by disks to the total area within the domain.

Traditional algorithms tackle disk packing by randomly distributing points within a domain, drawing a radius around those points, and decreasing the radius while increasing the number of disks. However, this fails when too many points are initially assigned near the domain’s borders.

Paolo Amore developed three algorithms to maximize the packing fraction for disks within regular polygons. He wanted to understand how the container’s shape influences the packing fraction and other properties of the system.

The first algorithm randomly scatters points inside a regular polygon. The points are treated like charges and moved about to find an equilibrium with the minimal total energy of the system. To mitigate clustering along the edges, the algorithm enforces repulsive borders.

“Algorithm two is based on a physical analogy we have all experienced: when one pours several objects inside a container, lets them settle, then provides a few additional (gentle) shake-ups, it may help to improve the packing,” Amore said.

Finally, a third algorithm quantitatively adjusts the configuration by counting the number of contacts each disk has and decreasing the space between close contacts.

Working together, the algorithms found the shape of the container impacts optimal packing. For example, hexagons and equilateral triangles have higher border density than squares.

Circle packing is a complex, multidisciplinary problem with many applications in physics including charge distribution and granular matter and testing optimization algorithms.

Source: “Circle packing in regular polygons,” by Paolo Amore, Physics of Fluids (2023). The article can be accessed at https://doi.org/10.1063/5.0140644 .

Related Topics
More Science
/
Article
Carefully constructed active layers enable these solar cells to achieve peak morphology and sun-absorbing power.
AAS
/
Article
Jupiter, Venus, and Mercury continue at dawn. The evening Moon meets Saturn while Fomalhaut looks on. Saturn’s own biggest moon casts its shadow onto Saturn’s globe, for one of the last times for the next 15 years.
/
Article
Ligand-assisted crystallization of perovskite increases photovoltaic performance of flexible solar cells
/
Article
Automation of the discovery of new materials is boosted with a software tool aimed at small angle scattering experiments.