Algorithms optimize circle packing in regular polygons
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 .
