Split Packing: Packing Circles into Triangles with Optimal Worst-Case Density

In the circle packing problem for triangular containers, one asks whether a given set of circles can be packed into a given triangle. Packing problems like this have been shown to be \(\mathsf {NP}\)-hard. In this paper, we present a new sufficient condition for packing circles into any right or obtuse triangle using only the circles’ combined area: It is possible to pack any circle instance whose combined area does not exceed the triangle’s incircle. This area condition is tight, in the sense that for any larger area, there are instances which cannot be packed.