Online Circle and Sphere Packing∗ | Zendy

Carla Négri Lintzmayer | Zendy; Flávio K. Miyazawa | Zendy; Eduardo C. Xavier | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Online Circle and Sphere Packing∗

Author(s) -

Carla Négri Lintzmayer,

Flávio K. 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research