The Split Packing algorithm  is an offline algorithm that packs a set of circles into shapes (triangles and squares) at an optimal packing density. In this paper, we develop an online alternative to Split Packing to handle an online sequence of insertions and deletions, where the algorithm is allowed to reallocate circles into new positions at a cost proportional to their areas. The algorithm can be used to pack circles into squares and right angled triangles. If only insertions are considered, our algorithm is also able to achieve optimal packing density as defined in our paper , with an amortized reallocation cost of O(c\log 1{c}) for squares, and O(c(1+s^2)1+s^21{c}) for right angled triangles, where s is the ratio of the lengths of the second shortest side to the shortest, when inserting a circle of area c. When insertions and deletions are considered, we achieve a packing density of (1-\epsilon) of the optimal, where \epsilon>0 can be made arbitrarily small, for an additional amortized reallocation cost of O(  c1{\epsilon}).
The Split Packing algorithm \mbox{%DIFAUXCMD splitpacking_ws, splitpacking is an offline algorithm that packs a set of circles into shapes (triangles and squares) at an optimal packing density. In this paper, we develop an online alternative to Split Packing to handle an online sequence of insertions and deletions, where the algorithm is allowed to reallocate circles into new positions at a cost proportional to their areas. The algorithm can be used to pack circles into squares and right angled triangles. If only insertions are considered, our algorithm is also able to achieve optimal packing density , with an amortised reallocation cost of O(c\log 1{c}) for squares, and O(c(1+s^2)1+s^21{c}) for right angled triangles, where s is the ratio of the lengths of the second shortest side to the shortest, when inserting a circle of area c. When insertions and deletions are considered, we achieve a packing density of (1-\epsilon) of the optimal, where \epsilon>0 can be made arbitrarily small, with an amortised reallocation cost of O( c(1+s^2)\log_{1+s^2 c1{\epsilon}).
A
\mbox{%DIFAUXCMD splitpacking_ws, splitpacking
D
as defined in our paper
R
amortized
amortised
R
for an additional amortized
with an amortised
A
c(1+s^2)\log_{1+s^2