Algorithms of optimal packing construction for planar compact sets

Authors

  • A.L. Kazakov Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
  • P.D. Lebedev N.N. Krasovskii Institute of Mathematics and Mechanics of UB RAS (IMM UB RAS)

DOI:

https://doi.org/10.26089/NumMet.v16r230

Keywords:

disk packing, Dirichlet zone, Voronoi diagram, optical geometric method, numerical algorithm, program complex

Abstract

The best packing problem for a prescribed number of equal disks in a compact planar set with their minimally possible radius is considered. An analytical algorithm for constructing the one disk best packing in a polygon in Euclidean space based on the maximization of the distance function from the boundary is proposed. An iteration algorithm based on the previous one is developed using the splitting into subsets (Dirichlet zones) with the aid of the Voronoi diagram. A numerical algorithm for packing in a nonconvex set in non-Euclidian metrics based on the optical geometric analogy is also proposed. A number of examples are numerically solved with a large number of packing elements and for a special non-Euclidian metrics.

Author Biographies

A.L. Kazakov

P.D. Lebedev

References

  1. Бухаров Д.С., Казаков А.Л. Программная система «Виголт» для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование: новые вычислительные технологии. 2012. 13, № 2. 65-74.
  2. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. 50-57.
  3. Ушаков В.Н., Матвийчук А.Р., Лебедев П.Д. Дефект стабильности в игровой задаче о сближении в момент // Вестник Удмуртского университета. Математика, механика, компьютерные науки. 2010. Вып. 3. 87-103.
  4. Лебедев П.Д., Бухаров Д.С. Аппроксимация многоугольников наилучшими наборами кругов // Известия Иркутского гос. университета. Математика. 2013. № 3. 72-87.
  5. Лебедев П.Д., Успенский А.А., Ушаков В.Н. Алгоритмы наилучшей аппроксимации плоских множеств объединениями кругов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 4. 88-99.
  6. Ушаков В.Н., Лахтин А.С., Лебедев П.Д. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве // Труды ИММ УрО РАН. 2014. 20, № 3. 291-308.
  7. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. М.: Мир, 1990.
  8. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Изд-во физико-математической литературы, 1958.
  9. Левенштейн В.И. О границах для упаковок в n-мерном евклидовом пространстве // Доклады АН СССР. 1979. 245, № 6. 1299-1303.
  10. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. 87-100.
  11. Лемперт А.А., Казаков А.Л., Бухаров Д.С. Математическая модель и программная система для решения задачи размещения логистических объектов // Управление большими системами. Вып. 41. M.: Инст. проблем управления РАН, 2013. 270-284.
  12. Szab’o P.G., Specht E. Packing up to 200 equal circles in a square // Models and Algorithms for Global Optimization. Optimization and Its Applications. Vol. 4. Heidelberg: Springer, 2007. 141-156.
  13. Casado L.G., Garcia I., Szab’o P.G., Csendes T. Packing equal circles in a square II. New results for up to 100 circles using the TAMSASS-PECS algorithm // Optimization Theory. Applied Optimization. Vol. 59. Heidelberg: Springer, 2001. 207-224.
  14. Mark’ot M.Cs., Csendes T. A new verified optimization technique for the «packing circles in a unit square» problems // SIAM Journal on Optimization. 2005. 16, N 1. 193-219.
  15. de Groot C., Peikert R., Würtz D. The optimal packing of ten equal circles in a square // IPS Research Report N 90-12. Zürich: Eidgenössische Technische Hochschule, 1990.
  16. Graham R.L., Lubachevsky B.D., Nurmela K.J., Östergard P.R. J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. 181, N 1-3. 139-154.
  17. Lubachevsky B.D., Graham R.L. Curved hexagonal packings of equal disks in a circle // Discrete Comput. Geom. 1997. 18, N 2. 179-194.
  18. Goldberg M. Packing of 14, 16, and 20 circles in a circle // Math. Mag. 1971. 44, N 3. 134-139.
  19. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985.
  20. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981.
  21. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
  22. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. М.: Физматлит, 2009.
  23. Дубровин Б.А., Новиков С.П., Фоменко А.Т. Современная геометрия. Методы и приложения. М.: Физматлит, 1986.
  24. Гаркави А.Л. О существовании наилучшей сети и наилучшего поперечника множества в банаховом пространстве // Успехи матем. наук. 1960. 15, вып. 2. 210-211.
  25. Казаков А.Л., Лемперт А.А., Бухаров Д.С. Об одном численном методе решения некоторых задач оптимизации, возникающих в транспортной логистике // Вестник Иркутского гос. техн. университета. 2011. 53, № 6. 6-12.
  26. Брусов В.С., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журн. вычисл. математики и мат. физики. 1971. 11, № 2. 304-312.
  27. Чен К., Джиблин П., Ирвинг А. MATLAB в математических исследованиях. М.: Мир, 2001.

Published

2015-06-12

How to Cite

Казаков А.Л., Лебедев П.Д. Algorithms of Optimal Packing Construction for Planar Compact Sets // Numerical methods and programming. 2015. 16. 307-317. doi 10.26089/NumMet.v16r230

Issue

Section

Section 1. Numerical methods and applications