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

Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости

Авторы

  • А.Л. Казаков
  • П.Д. Лебедев

Ключевые слова:

упаковка кругов
зона Дирихле
диаграмма Вороного
оптико-геометрический метод
вычислительный алгоритм
программный комплекс

Аннотация

Рассматривается задача об упаковке заданного числа равных кругов в компактное множество на плоскости при наибольшем возможном их радиусе. Разработан аналитический алгоритм отыскания наилучшей упаковки одного круга в многоугольник в евклидовом пространстве, основанный на максимизации функции расстояния от границы. На его основе создан алгоритм итерационного улучшения упаковки в выпуклое множество, использующий разбиение на подмножества (зоны Дирихле) с помощью диаграммы Вороного. Предложен численный алгоритм построения упаковки для случаев невыпуклого множества и неевклидовой метрики, основанный на оптико-геометрической аналогии. Проведено численное решение ряда примеров при большом количестве элементов упаковки в евклидовом пространстве и для одной специальной неевклидовой метрики.

Новые вычислительные технологии

Загрузки

Опубликован

2015-06-12

Выпуск

Том 16 (2015): Выпуск 2.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.Л. Казаков

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск
• заведующий лабораторией

П.Д. Лебедев

Институт математики и механики имени Н.Н. Красовского УрО РАН (ИММ УрО РАН)
ул. Софьи Ковалевской, 16, 620108, Екатеринбург
• научный сотрудник

Библиографические ссылки

  1. D. S. Bukharov and A. L. Kazakov, “VIGOLT System for Solving Transport Logistics Optimization Problems,” Vychisl. Metody Programm. 13, 65-74 (2012).
  2. A. L. Kazakov and A. A. Lempert, “An Approach to Optimization in Transport Logistics,” Avtom. Telemekh. No. 7, 50-57 (2011) [Autom. Remote Control 72 (7), 1396-1404 (2011)].
  3. V. N. Ushakov, A. R. Matviychuk, and P. D. Lebedev, “Defect of Stability in Game-Pursuit Problem,” Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki No. 3, 87-103 (2010).
  4. P. D. Lebedev and D. S. Bukharov, “Approximation of Polygons with the Best Set of Circles,” Izv. Irkutsk Univ. Ser. Mat. No. 3, 72-87 (2013).
  5. P. D. Lebedev, A. A. Uspenskii, and V. N. Ushakov, “Algorithms of the Best Approximations of the Flat Sets by the Union of Circles,” Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki No. 4, 88-99 (2013).
  6. V. N. Ushakov, A. S. Lakhtin, and P. D. Lebedev, “Optimization of the Hausdorff Distance between Sets in Euclidean Space,” Tr. Inst. Mat. Mekh. UrO RAN 20 (3), 291-308 (2014).
  7. J. H. Conway and N. J. A. Sloane, Sphere Packing, Lattices and Groups (Springer, New York, 1988; Mir, Moscow, 1990).
  8. L. F. Töth, Lagerungen in der Ebene, auf der Kugel und im Raum (Springer, Berlin, 1957; Fizmatlit, Moscow, 1958).
  9. V. I. Levenshtein, “Boundaries for Packings in n-Dimensional Euclidean Space,” Dokl. Akad. Nauk SSSR 245 (6), 1299-1303 (1979).
  10. A. L. Kazakov, A. A. Lempert, and D. S. Bukharov, “On Segmenting Logistical Zones for Servicing Continuously Developed Consumers,” Avtom. Telemekh. No. 6, 87-100 (2013) [Autom. Remote Control 74 (6), 968-977 (2013)].
  11. A. A. Lempert, A. L. Kazakov, and D. S. Bukharov, “Mathematical Model and Program System for Solving a Problem of Logistic Objects Placement,” in Control of Large Systems (Trapeznikov Inst. Control Sci., Moscow, 2013), Issue 41, pp. 270-284.
  12. P. G. Szabó and E. Specht, “Packing up to 200 Equal Circles in a Square,” in Models and Algorithms for Global Optimization. Optimization and Its Applications (Springer, Heidelberg, 2007), Vol. 4, pp. 141-156.
  13. L. G. Casado, I. Garcia, P. G. Szabó, and T. Csendes, “Packing Equal Circles in a Square II. New Results for up to 100 Circles Using the TAMSASS-PECS Algorithm,” in Optimization Theory. Applied Optimization (Springer, Heidelberg, 2001), Vol. 59, pp. 207-224.
  14. M. C. Markót and T. Csendes, “A New Verified Optimization Technique for the ’Packing Circles in a Unit Square’ Problems,” SIAM J. Optim. 16 (1), 193-219 (2005).
  15. C. de Groot, R. Peikert, and D. Würtz, The Optimal Packing of Ten Equal Circles in a Square , Research Report No. 90-12 (Eidgenössische Tech. Hochschule, Zürich, 1990).
  16. R. L. Graham, B. D. Lubachevsky, K. J. Nurmela, and P. R. J. Östergard, “Dense Packings of Congruent Circles in a Circle,” Discrete Math. 181 (1-3), 139-154 (1998).
  17. B. D. Lubachevsky and R. L. Graham, “Curved Hexagonal Packings of Equal Disks in a Circle,” Discrete Comput. Geom. 18 (2), 179-194 (1997).
  18. M. Goldberg, “Packing of 14, 16, 17 and 20 Circles in a Circle,” Math. Mag. 44 (3), 134-139 (1971).
  19. K. Leichtweiss, Konvexe Mengen (Springer, Berlin, 1980; Nauka, Moscow, 1985).
  20. V. F. Dem’yanov and L. V. Vasiliev, Nondifferentiated Optimization (Nauka, Moscow, 1981) [in Russian].
  21. B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983) [in Russian].
  22. L. M. Mestetsky, Continuous Morphology of Binary Images: Shapes, Frames, Circulars (Fizmatlit, Moscow, 2009) [in Russian].
  23. B. A. Dubrovin, S. P. Novikov, and A. T. Fomenko, Modern Geometry (Fizmatlit, Moscow, 1986) [in Russian].
  24. A. L. Garkavi, “Existence of the Best Net and the Best Width for Set in a Banach Space,” Usp. Mat. Nauk 15 (2), 210-211 (1960).
  25. A. L. Kazakov, A. A. Lempert, and D. S. Bukharov, “On a Numerical Method to Solve Some Optimization Problems Occurring in Transport Logistics,” Vestn. Irkutsk Tekh. Univ. 53 (6), 6-12 (2011).
  26. V. S. Brusov and S. A. Piyavskii, “A Computational Algorithm for Optimally Covering a Plane Region,” Zh. Vychisl. Mat. Mat. Fiz. 11 (2), 304-312 (1971) [USSR Comput. Math. Math. Phys. 11 (2), 17-27 (1971)].
  27. K. Chen, P. J. Giblin, and A. Irving, Mathematical Explorations with MATLAB (Cambridge Univ. Press, New York, 1999; Mir, Moscow, 2001).