Online Circle and Sphere Packing - Lintzmayer, Carla Negri; Miyazawa, Flávio Keidi; Xavier, Eduardo Candido (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2018.3158, 2018)
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.