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 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. A similar result for square containers has been established earlier this year, using the versatile, divide-and-conquer-based Split Packing algorithm. In this paper, we present a generalized, weighted version of this approach, allowing us to construct packings of circles into asymmetric triangles. It seems crucial to the success of these results that Split Packingdoes not depend on an orthogonal subdivision structure. Beside realizing all packings below the critical density bound, our algorithm can also be used as a constant-factor approximation algorithm when looking for the smallest non-acute triangle of a given side ratio in which a given set of circles can be packed . An interactive visualization of the Split Packing approach and other related material can be found at URL
In the classic circle packing problem , one asks whether a given set of circles can be packed into a given container . Packing problems like this have been shown to be NP-hard. In this paper, we present new sufficient conditions for packing circles into square and triangular containers, using only the sum of the circles' areas: For square containers, it is possible to pack any set of circles with a combined area of up to approximately 53.90\% of the square's area. And when the container is a right or obtuse triangle, any set of circles whose combined area does not exceed the triangle's incircle can be packed. These area conditions are tight, in the sense that for any larger areas , there are sets of circles which cannot be packed. Similar results have long been known for squares, but to the best of our knowledge, we give the first results of this type for circular objects. Our proofs are constructive: We describe a versatile, divide-and-conquer-based algorithm for packing circles into various container shapes with optimal worst-case density. It employs an elegant subdivision scheme that recursively splits the circles into two groups and then packs these into subcontainers. We call this algorithm "Split Packing". It can be used as a constant-factor approximation algorithm when looking for the smallest container in which a given set of circles can be packed , due to its polynomial runtime. A browser-based, interactive visualization of the Split Packing approach and other related material can be found at URL
A
classic
D
for triangular containers
R
triangle
container
R
a new sufficient condition
new sufficient conditions
R
any right or obtuse triangle
square and triangular containers,
R
circles' combined area: It
sum of the circles' areas: For square containers, it
R
circle instance
set of circles with a combined area of up to approximately 53.90\% of the square's area. And when the container is a right or obtuse triangle, any set of circles
R
. This area condition is
can be packed. These area conditions are
R
area
areas
R
instances
sets of circles
R
A similar result for square containers has been established earlier this year, using the versatile,
Similar results have long been known for squares, but to the best of our knowledge, we give the first results of this type for circular objects. Our proofs are constructive: We describe a versatile,
R
Split Packing algorithm. In this paper, we present a generalized, weighted version of this approach, allowing us to construct packings of circles into asymmetric triangles. It seems crucial to the success of these results that Split Packingdoes not depend on an orthogonal subdivision structure. Beside realizing all packings below the critical density bound, our algorithm can also
algorithm for packing circles into various container shapes with optimal worst-case density. It employs an elegant subdivision scheme that recursively splits the circles into two groups and then packs these into subcontainers. We call this algorithm "Split Packing". It can
R
non-acute triangle of a given side ratio
container
R
. An
, due to its polynomial runtime. A browser-based,