Online Circle and Sphere Packing∗

  • Carla Negri Lintzmayer
  • Flávio Keidi Miyazawa
  • Eduardo Candido Xavier
DOI: https://doi.org/10.5753/etc.2018.3158

Resumo


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.

Publicado
26/07/2018
Como Citar

Selecione um Formato
LINTZMAYER, Carla Negri; MIYAZAWA, Flávio Keidi; XAVIER, Eduardo Candido. Online Circle and Sphere Packing∗. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3158.