RESEARCH.md

Relevant Research

On the topic of circle packing, optimisation, linear programming, ...

Mathematics

• Circle packing
  • Umwandlung in planare Graphen (Circle Packing Theorem, siehe auch Computing Circle Packing Representations of Planar Graphs)
  • Verbindung zu Parität
• Soddy-Kreis

Critical packing densitiy $\delta^*$ for disks in a square is $\frac{\pi}{3+2\sqrt{2}}\approx 0.539$ as shown with Split Packing by Morr, Fekete and Scheffer.

• S. P. Fekete, S. Morr, and C. Scheffer. Split packing: Algorithms for packing circles with optimal worst-case density. Discrete & Computational Geometry, 2018.
• S. Morr. Split packing: An algorithm for packing circles with optimal worst-case density. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 99–109, 2017.

The benchmark for circle packing: Packomania.

Literature

Circle Packing

• Galiev, S. I., & Lisafina, M. S. (2013). Linear models for the approximate solution of the problem of packing equal circles into a given domain. European Journal of Operational Research, 230(3), 505–514. https://doi.org/10.1016/J.EJOR.2013.04.050
• Becker, A. T., Fekete, S. P., Keldenich, P., Morr, S., & Scheffer, C. (2019). Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition). DROPS-IDN/10467, 129. https://doi.org/10.4230/LIPICS.SOCG.2019.63
• Specht, E. (2023, March 1). Packomania. http://www.packomania.com
• Huang, W. Q., Li, Y., Akeb, H., & Li, C. M. (2005). Greedy algorithms for packing unequal circles into a rectangular container. Journal of the Operational Research Society, 56(5), 539–548. https://doi.org/10.1057/PALGRAVE.JORS.2601836/METRICS
• López Soto, C. O. (2013). Formulation space search for two-dimensional packing problems [Brunel University School of Information Systems, Computing and Mathematics Theses PhD Theses]. http://bura.brunel.ac.uk/handle/2438/7455
• López, C. O., & Beasley, J. E. (2011). A heuristic for the circle packing problem with a variety of containers. European Journal of Operational Research, 214(3), 512–525. https://doi.org/10.1016/J.EJOR.2011.04.024
• Addis, B., Locatelli, M., & Schoen, F. (2008). Efficiently packing unequal disks in a circle. Operations Research Letters, 36(1), 37–42. https://doi.org/10.1016/J.ORL.2007.03.001
• Dong, S., Lee, Y. T., & Quanrud, K. (2019). Computing Circle Packing Representations of Planar Graphs. https://doi.org/10.48550/arxiv.1911.00612
• He, K., Huang, M., & Yang, C. (2015). An action-space-based global optimization algorithm for packing circles into a square container. Computers & Operations Research, 58, 67–74. https://doi.org/10.1016/J.COR.2014.12.010

See also

Linear Programming

• Effiziente Algorithmen. Lineare Programme 1/2. Walter Unger
• Introduction to Operations Research 9th Edition. Hillier, Lieberman

Exploratory concepts

• Quantum computing: QuTiP, Quantum Toolbox in Python
• AI: TensorFlow

AMPL

ampl.com

AMPL Book

https://pifop.com/ https://neos-server.org/neos/