Open AccessOnline Circle and Sphere Packing∗
Author(s) -
Carla Négri Lintzmayer,
Flávio Keidi Miyazawa,
Eduardo C. Xavier
Publication year - 2018
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2018.3158
Subject(s) - circle packing , isosceles triangle , square (algebra) , bounded function , packing problems , sphere packing , combinatorics , space (punctuation) , bin packing problem , unit (ring theory) , computer science , mathematics , unit cube , algorithm , geometry , mathematical analysis , mathematics education , bin , operating system
In the Online Circle Packing in Squares, circles arrive one at a time and we need to pack them into the minimum number of unit square bins. We improve the previous best-known competitive ratio for the bounded space version from 2.439 to 2.3536 and we also give an unbounded space algorithm. Our algorithms also apply to the Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes, for which no previous results were known.