Split packing: an algorithm for packing circles with optimal worst-case density

In the classic circle packing problem, one asks whether a given set of circles can be packed into the unit square. This problem is known to be NP-hard. In this paper, we present a new sufficient condition using only the circles' combined area: It is possible to pack any circle instance with a combined area of up to ≈ 0.5390. This bound is tight, in the sense that for any larger combined area, there are instances which cannot be packed, which is why we call this number the problem's critical density. Similar results have long been known for squares, but to the best of our knowledge, this paper gives the first results of this type for circular objects.