Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

CGGC Seminar: Dense Packing of Congruent Circles in Free-form Non-convex Containers
event speaker icon
Jinesh Machchhar (CS,​​Technnion)​​
event date icon
Sunday, 19.03.2017, 13:30
event location icon
Room 337 Taub Bld.
This work proposes an algorithm for computing dense packings of congruent circles inside general 2D containers. Unlike the previous approaches which accept as containers, only simple, symmetric shapes such as circles, rectangles and triangles, our method works for any container with a general, freeform (spline) boundary.

In contrast to most previous approaches which cast the problem into a non-convex optimization problem, our method attempts to maximize the number of packed circles via a perturbation approach and consists of two main phases.

In the first phase, an initial packing is computed by placing circles in spiraling layers, starting along the boundary of the container. The next phase simulates the shaking of a container under gravity, thereby making room for additional circles by perturbing the existing circles. While the general circle packing problem is known to be NP-hard, our method proposes heuristics which lead to dense packings.

Comparison of results with previous approaches on simple, symmetric shapes shows the effectiveness of our algorithm while results of packing inside freeform containers demonstrates the generality of our algorithm.

This is joint work with Gershon Elber.