Um QPTAS para o Problema de Empacotamento de Círculos em Linha

• Elisa Dell’Arriva UNICAMP
• Flávio K. Miyazawa UNICAMP

DOI: https://doi.org/10.5753/etc.2023.230684

Abstract

In the circle in-line packing problem, we have a list of circles that must be placed side by side over a horizontal line, so that each circle touches the line only at its lowest point. The objective is to minimize the distance between the leftmost and the rightmost points of the circles that define the extremes of the packing. In 2018, [Dürr et al. 2018] presented a QPTAS for the particular case where the itens are isosceles right triangles. In this text, we present an adaptation of the QPTAS to the circle in-line packing problem.

References

Alt, H., Buchin, K., Chaplick, S., Cheong, O., Kindermann, P., Knauer, C., and Stehn, F. (2018). Placing your coins on a shelf. Journal of Computational Geometry, 9:312–327.

Cohn, H., Kumar, A., Miller, S., Radchenko, D., and Viazovska, M. (2017). The sphere packing problem in dimension 24. Annals of Mathematics, 185(3).

Dell’Arriva, E. (2021). In-line packing of circles. Master’s thesis, Universidade Estadual de Campinas.

Dürr, C., Hanzálek, Z., Konrad, C., Seddik, Y., Sitters, R., Óscar C. Vásquez, and Woeginger, G. (2018). The triangle scheduling problem. Journal of Scheduling, 21:305–312.

Hales, T. and Ferguson, S. (2006). A formulation of the kepler conjecture. Discrete & Computational Geometry, 36:21–69.

Kepler, J. (1611). Strena seu de nive sexangula (the six-cornered snowflake).

Miyazawa, F. K., Pedrosa, L. L. C., Schouery, R. C. S., Sviridenko, M., and Wakabayashi, Y. (2016). Polynomial-time approximation schemes for circle and other packing problems. Algorithmica, 76(2):536–568.

Miyazawa, F. K. and Wakabayashi, Y. (2022). Techniques and results on approximation algorithms for packing circles. São Paulo Journal of Mathematical Sciences, 16(1):585–615.

Viazovska, M. (2017). The sphere packing problem in dimension 8. Annals of Mathematics, 185(3).