# A Reallocation Algorithm for Online Split Packing of Circles.

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 \frac{1}{c})$ for squares, and $O(c(1+s^2)\log_{1+s^2}\frac{1}{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(c\frac{1}{\epsilon})$.

Publisher URL: http://arxiv.org/abs/1802.05873

DOI: arXiv:1802.05873v1

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesnâ€™t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.