Алгоритмы построения оптимального покрытия плоских фигур в динамической метрике
Ключевые слова:
оптимальное покрытие, волновой фронт, динамическая метрика, чебышёвский центр
Аннотация
Рассматривается задача о построении наиболее эффективного (тончайшего) покрытия выпуклого множества на плоскости набором однотипных элементов. В качестве меры удаленности двух точек множества выступает наименьшее время, за которое можно попасть из одной точки в другую, и границей каждого покрывающего круга является изохрона. Подобные задачи возникают в приложениях, в частности, в системах гидролокации и подводного наблюдения. Для решения задач покрытия такими кругами и шарами ранее нами были предложены алгоритмы, основанные как на вариационных принципах, так и на основе геометрических методов. Целью настоящей статьи является построение покрытий в случае, когда характеристики среды изменяются во времени. Для решения указанной задачи предложен вычислительный алгоритм, основанный на теории волновых фронтов. Доказано утверждение о свойствах метода. Выполнены иллюстрирующие расчеты.
Литература
1. Tóth L.F. Regular figures. London: Pergamon Press, 1964.
2. Tóth L.F. Solid circle-packings and circle-coverings // Studia Scientiarum Mathematicarum Hungarica. 1968. Vol. 3. P. 401-409.
3. Heppes A. Covering a planar domain with sets of small diameter // Periodica Mathematica Hungarica. 2006. Vol. 53. P. 157-168. https://doi.org/10.1007/s10998-006-0029-9
4. Szabó P.G., Specht E. Packing up to 200 equal circles in a square // Models and algorithms for global optimization. New York: Springer, 2007. P. 141-156. https://doi.org/10.1007/978-0-387-36721-7_9
5. Tóth G.F. Thinnest covering of a circle by eight, nine, or ten congruent circles // Combinatorial and Computational Geometry. 2005. Vol. 52. P. 361-376.
6. Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 2014. Т. 21. Вып. 1. C. 84-102. http://mi.mathnet.ru/da762
7. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. Issue 1. P. 40-46. https://doi.org/10.1515/agms-2017-0002
8. Specht E. Packomania [Electronic Resources URL: http://www.packomania.com]. Дата обращения 10.06.2022.
9. Erich's Packing Center [Electronic Resources URL: https://erich-friedman.github.io/packing/index.html]. Дата обращения 10.06.2022.
10. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. М.: Мир, 1990.
11. Hifi L.M., M'Hallah R. A literature review on circle and sphere packing problems: models and methodologies // Advances in Operations Research. 2009. Vol. 2009. Article ID: 150624. https://doi.org/10.1155/2009/150624
12. Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles // Experimental Mathematics. 2000. Vol. 9. Issue 2. P. 241-250. https://doi.org/10.1080/10586458.2000.10504649
13. Galiev S.I., Lisafina M.S. Linear models for the approximate solution of the problem of packing equal circles into a given domain // European Journal of Operation Research. 2013. Vol. 230. Issue 3. P. 505-514. https://doi.org/10.1016/j.ejor.2013.04.050
14. Litvinchev I., Ozuna L.Integer programming formulations for approximate packing circles in a rectangular container // Mathematical Problems in Engineering. 2014. Vol. 2014. Article ID: 317697. https://doi.org/10.1155/2014/317697
15. Stoyan Y.G., Patsuk V.M. Covering a compact polygonal set by identical circles // Computational Optimization and Applications. 2010. Vol. 46. Issue 1. P. 75-92. https://doi.org/10.1007/s10589-008-9191-8
16. Bánhelyi B., Palatinus E., Lévai B.L. Optimal circle covering problems and their applications // Central European Journal of Operations Research. 2015. Vol. 23. Issue 4. P. 815-832. https://doi.org/10.1007/s10100-014-0362-7
17. Pardo E.G., Mladenović N., Pantrigo J.J., Duarte A. Variable formulation search for the cutwidth minimization problem // Applied Soft Computing. 2013. Vol. 13. Issue 5. P. 2242-2252. https://doi.org/10.1016/j.asoc.2013.01.016
18. López C.O., Beasley J.E. A heuristic for the circle packing problem with a variety of containers // European Journal of Operational Research. 2011. Vol. 214. Issue 3. P. 512-525. https://doi.org/10.1016/j.ejor.2011.04.024
19. López C.O., Beasley J.E. Packing a fixed number of identical circles in a circular container with circular prohibited areas // Optimization Letters. 2019. Vol. 13. Issue 7. P. 1449-1468. https://doi.org/10.1007/s11590-018-1351-x
20. Huang W., Ye T. Greedy vacancy search algorithm for packing equal circles in a square // Operations Research Letters. 2010. Vol. 38. Issue 5. P. 378-382. https://doi.org/10.1016/j.orl.2010.07.004
21. Graham R.L., Lubachevsky B.D., Nurmela K.J., Östergård P.R.J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. Vol. 181. Issues 1-3. P. 139-154. https://doi.org/10.1016/S0012-365X(97)00050-2
22. Lubachevsky B.D. How to simulate billiards and similar systems // Journal of Computational Physics. 1991. Vol. 94. Issue 2. P. 255-283. https://doi.org/10.1016/0021-9991(91)90222-7
23. Torres-Escobar R., Marmolejo-Saucedo J.A., Litvinchev I. Binary monkey algorithm for approximate packing non-congruent circles in a rectangular container // Wireless Networks. 2020. Vol. 26. Issue 7. P. 4743-4752. https://doi.org/10.1007/S11276-018-1869-Y
24. Макагонов Е.П. Эффективное покрытие пространства координационными сферами - основной принцип строения и конституции минералов // Минералогия. 2015. № 4. C. 3-18. https://www.elibrary.ru/item.asp?id=25012694
25. Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал вычислительной математики и математической физики. 2010. Т. 50. № 4. С. 757-769. https://elibrary.ru/item.asp?id=13726048
26. Kazakov A.L., Lempert A.A. On mathematical models for optimization problem of logistics infrastructure // International Journal of Artificial Intelligence. 2015. Vol. 13. No. 1. P. 200-210. http://www.ceser.in/ceserp/index.php/ijai/article/view/3537
27. Erzin A., Lagutkina N., Ioramishvili N. Barrier covering in 2d using mobile sensors with circular coverage areas // Learning and intelligent optimization. Cham: Springer, 2020. P. 342-354. https://doi.org/10.1007/978-3-030-38629-0_28
28. Han C., Sun L., Xiao F., Guo J. An energy efficiency node scheduling model for spatial-temporal coverage optimization in 3d directional sensor networks // IEEE Access. 2016. Vol. 4. P. 4408-4419. https://doi.org/10.1109/ACCESS.2016.2592184
29. Arun D., Pais A.R. Optimal placement of sensor nodes for water quality measurement // 2015 Twelfth International Conference on Wireless and Optical Communications Networks (WOCN). IEEE, 2015. https://doi.org/10.1109/WOCN.2015.8064508
30. Печенкин В.В., Королёв М.С. Оптимизация размещения средств наблюдения в трёхмерной сцене с целью минимизации "слепых" зон // Компьютерная оптика. 2017. Т. 41. № 2. С. 245-253. https://doi.org/10.18287/2412-6179-2017-41-2-245-253
31. Jun S., Chang T.-W., Jeong H., Lee S. Camera placement in smart cities for maximizing weighted coverage with budget limit // IEEE Sensors Journal. 2017. Vol. 17. Issue 23. P. 7694-7703. https://doi.org/10.1109/jsen.2017.2723481
32. Wu H., Zhu H., Han X. An improved $k$-angle coverage algorithm for multimedia wireless sensor networks based on two-layer tabu search // Peer-to-Peer Networking and Applications. 2021. Vol. 15. Issue 1. P. 28-44. https://doi.org/10.1007/s12083-021-01188-1
33. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. Вып. 7. С. 50-57. http://mi.mathnet.ru/at2243
34. Келлер Дж.Б., Пападакис Дж.С. Распространение волн и подводная акустика. М.: Мир, 1980.
35. Orlando D., Ehlers F. Advances in multistatic sonar // Sonar systems. London: IntechOpen, 2011.
36. Фищенко В.К., Зимин П.С., Зацерковный А.В., Гончарова А.А., Суботэ А.Е., Голик А.В. Стационарные системы подводного видеонаблюдения: возможности применения для мониторинга биоты прибрежных акваторий залива Петра Великого (Японское море) // Вестник Дальневосточного отделения Российской академии наук. 2018. № 1. С. 149-160. http://www.vestnikdvo.ru/index.php/vestnikdvo/article/view/30
37. Казаков А.Л., Лемперт А.А., Нгуен Г.Л. Алгоритм построения оптимальных покрытий равными кругами невыпуклых многоугольников с неевклидовой метрикой // Вестник Иркутского государственного технического университета. 2016. № 5 (112). С. 45-55. https://doi.org/10.21285/1814-3520-2016-5-45-55
38. Lempert A.A., Le Q.M. Multiple covering of a closed set on a plane with non-Euclidean metrics // IFAC-PapersOnLine. 2018. Vol. 51. No. 32. P. 850-854. https://doi.org/10.1016/j.ifacol.2018.11.439
39. Lempert A.A., Kazakov A.L., Le Q.M. On reserve and double covering problems for the sets with non-Euclidean metrics // Yugoslav Journal of Operations Research. 2019. Vol. 29. Issue 1. P. 69-79. https://doi.org/10.2298/yjor171112010l
40. Kazakov A.L., Lempert A.A., Ta T.T. The sphere packing problem into bounded containers in three-dimension non-Euclidean space // IFAC-PapersOnLine. 2018. Vol. 51. Issue 32. P. 782-787. https://doi.org/10.1016/j.ifacol.2018.11.450
41. Лебедев П.Д., Казаков А.Л. Построение оптимальных покрытий выпуклых плоских фигур кругами различного радиуса // Труды Института математики и механики УрО РАН. 2019. Т. 25. № 2. С. 137-148. https://doi.org/10.21538/0134-4889-2019-25-2-137-148
42. Лебедев П.Д. Итерационные методы построения аппроксимаций оптимальных покрытий невыпуклых плоских множеств// Челябинский физико-математический журнал. 2019. Т. 4. № 1. С. 5-17. https://doi.org/10.24411/2500-0101-2019-14101
43. Preparata F.P., Shamos M.I.Computational geometry: An introduction. New York: Springer, 1985. https://doi.org/10.1007/978-1-4612-1098-6
44. Казаков А.Л., Лебедев П.Д. Алгоритмы построения наилучших $n$-сетей в метрических пространствах // Автоматика и телемеханика. 2017. Вып. 7. С. 141-155. http://mi.mathnet.ru/at14837
45. Лебедев П.Д. Программа вычисления оптимального покрытия полусферы набором сферических сегментов. Свидетельство о государственной регистрации № 2015661543 от 29.10.2015.
2. Tóth L.F. Solid circle-packings and circle-coverings // Studia Scientiarum Mathematicarum Hungarica. 1968. Vol. 3. P. 401-409.
3. Heppes A. Covering a planar domain with sets of small diameter // Periodica Mathematica Hungarica. 2006. Vol. 53. P. 157-168. https://doi.org/10.1007/s10998-006-0029-9
4. Szabó P.G., Specht E. Packing up to 200 equal circles in a square // Models and algorithms for global optimization. New York: Springer, 2007. P. 141-156. https://doi.org/10.1007/978-0-387-36721-7_9
5. Tóth G.F. Thinnest covering of a circle by eight, nine, or ten congruent circles // Combinatorial and Computational Geometry. 2005. Vol. 52. P. 361-376.
6. Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 2014. Т. 21. Вып. 1. C. 84-102. http://mi.mathnet.ru/da762
7. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. Issue 1. P. 40-46. https://doi.org/10.1515/agms-2017-0002
8. Specht E. Packomania [Electronic Resources URL: http://www.packomania.com]. Дата обращения 10.06.2022.
9. Erich's Packing Center [Electronic Resources URL: https://erich-friedman.github.io/packing/index.html]. Дата обращения 10.06.2022.
10. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. М.: Мир, 1990.
11. Hifi L.M., M'Hallah R. A literature review on circle and sphere packing problems: models and methodologies // Advances in Operations Research. 2009. Vol. 2009. Article ID: 150624. https://doi.org/10.1155/2009/150624
12. Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles // Experimental Mathematics. 2000. Vol. 9. Issue 2. P. 241-250. https://doi.org/10.1080/10586458.2000.10504649
13. Galiev S.I., Lisafina M.S. Linear models for the approximate solution of the problem of packing equal circles into a given domain // European Journal of Operation Research. 2013. Vol. 230. Issue 3. P. 505-514. https://doi.org/10.1016/j.ejor.2013.04.050
14. Litvinchev I., Ozuna L.Integer programming formulations for approximate packing circles in a rectangular container // Mathematical Problems in Engineering. 2014. Vol. 2014. Article ID: 317697. https://doi.org/10.1155/2014/317697
15. Stoyan Y.G., Patsuk V.M. Covering a compact polygonal set by identical circles // Computational Optimization and Applications. 2010. Vol. 46. Issue 1. P. 75-92. https://doi.org/10.1007/s10589-008-9191-8
16. Bánhelyi B., Palatinus E., Lévai B.L. Optimal circle covering problems and their applications // Central European Journal of Operations Research. 2015. Vol. 23. Issue 4. P. 815-832. https://doi.org/10.1007/s10100-014-0362-7
17. Pardo E.G., Mladenović N., Pantrigo J.J., Duarte A. Variable formulation search for the cutwidth minimization problem // Applied Soft Computing. 2013. Vol. 13. Issue 5. P. 2242-2252. https://doi.org/10.1016/j.asoc.2013.01.016
18. López C.O., Beasley J.E. A heuristic for the circle packing problem with a variety of containers // European Journal of Operational Research. 2011. Vol. 214. Issue 3. P. 512-525. https://doi.org/10.1016/j.ejor.2011.04.024
19. López C.O., Beasley J.E. Packing a fixed number of identical circles in a circular container with circular prohibited areas // Optimization Letters. 2019. Vol. 13. Issue 7. P. 1449-1468. https://doi.org/10.1007/s11590-018-1351-x
20. Huang W., Ye T. Greedy vacancy search algorithm for packing equal circles in a square // Operations Research Letters. 2010. Vol. 38. Issue 5. P. 378-382. https://doi.org/10.1016/j.orl.2010.07.004
21. Graham R.L., Lubachevsky B.D., Nurmela K.J., Östergård P.R.J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. Vol. 181. Issues 1-3. P. 139-154. https://doi.org/10.1016/S0012-365X(97)00050-2
22. Lubachevsky B.D. How to simulate billiards and similar systems // Journal of Computational Physics. 1991. Vol. 94. Issue 2. P. 255-283. https://doi.org/10.1016/0021-9991(91)90222-7
23. Torres-Escobar R., Marmolejo-Saucedo J.A., Litvinchev I. Binary monkey algorithm for approximate packing non-congruent circles in a rectangular container // Wireless Networks. 2020. Vol. 26. Issue 7. P. 4743-4752. https://doi.org/10.1007/S11276-018-1869-Y
24. Макагонов Е.П. Эффективное покрытие пространства координационными сферами - основной принцип строения и конституции минералов // Минералогия. 2015. № 4. C. 3-18. https://www.elibrary.ru/item.asp?id=25012694
25. Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал вычислительной математики и математической физики. 2010. Т. 50. № 4. С. 757-769. https://elibrary.ru/item.asp?id=13726048
26. Kazakov A.L., Lempert A.A. On mathematical models for optimization problem of logistics infrastructure // International Journal of Artificial Intelligence. 2015. Vol. 13. No. 1. P. 200-210. http://www.ceser.in/ceserp/index.php/ijai/article/view/3537
27. Erzin A., Lagutkina N., Ioramishvili N. Barrier covering in 2d using mobile sensors with circular coverage areas // Learning and intelligent optimization. Cham: Springer, 2020. P. 342-354. https://doi.org/10.1007/978-3-030-38629-0_28
28. Han C., Sun L., Xiao F., Guo J. An energy efficiency node scheduling model for spatial-temporal coverage optimization in 3d directional sensor networks // IEEE Access. 2016. Vol. 4. P. 4408-4419. https://doi.org/10.1109/ACCESS.2016.2592184
29. Arun D., Pais A.R. Optimal placement of sensor nodes for water quality measurement // 2015 Twelfth International Conference on Wireless and Optical Communications Networks (WOCN). IEEE, 2015. https://doi.org/10.1109/WOCN.2015.8064508
30. Печенкин В.В., Королёв М.С. Оптимизация размещения средств наблюдения в трёхмерной сцене с целью минимизации "слепых" зон // Компьютерная оптика. 2017. Т. 41. № 2. С. 245-253. https://doi.org/10.18287/2412-6179-2017-41-2-245-253
31. Jun S., Chang T.-W., Jeong H., Lee S. Camera placement in smart cities for maximizing weighted coverage with budget limit // IEEE Sensors Journal. 2017. Vol. 17. Issue 23. P. 7694-7703. https://doi.org/10.1109/jsen.2017.2723481
32. Wu H., Zhu H., Han X. An improved $k$-angle coverage algorithm for multimedia wireless sensor networks based on two-layer tabu search // Peer-to-Peer Networking and Applications. 2021. Vol. 15. Issue 1. P. 28-44. https://doi.org/10.1007/s12083-021-01188-1
33. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. Вып. 7. С. 50-57. http://mi.mathnet.ru/at2243
34. Келлер Дж.Б., Пападакис Дж.С. Распространение волн и подводная акустика. М.: Мир, 1980.
35. Orlando D., Ehlers F. Advances in multistatic sonar // Sonar systems. London: IntechOpen, 2011.
36. Фищенко В.К., Зимин П.С., Зацерковный А.В., Гончарова А.А., Суботэ А.Е., Голик А.В. Стационарные системы подводного видеонаблюдения: возможности применения для мониторинга биоты прибрежных акваторий залива Петра Великого (Японское море) // Вестник Дальневосточного отделения Российской академии наук. 2018. № 1. С. 149-160. http://www.vestnikdvo.ru/index.php/vestnikdvo/article/view/30
37. Казаков А.Л., Лемперт А.А., Нгуен Г.Л. Алгоритм построения оптимальных покрытий равными кругами невыпуклых многоугольников с неевклидовой метрикой // Вестник Иркутского государственного технического университета. 2016. № 5 (112). С. 45-55. https://doi.org/10.21285/1814-3520-2016-5-45-55
38. Lempert A.A., Le Q.M. Multiple covering of a closed set on a plane with non-Euclidean metrics // IFAC-PapersOnLine. 2018. Vol. 51. No. 32. P. 850-854. https://doi.org/10.1016/j.ifacol.2018.11.439
39. Lempert A.A., Kazakov A.L., Le Q.M. On reserve and double covering problems for the sets with non-Euclidean metrics // Yugoslav Journal of Operations Research. 2019. Vol. 29. Issue 1. P. 69-79. https://doi.org/10.2298/yjor171112010l
40. Kazakov A.L., Lempert A.A., Ta T.T. The sphere packing problem into bounded containers in three-dimension non-Euclidean space // IFAC-PapersOnLine. 2018. Vol. 51. Issue 32. P. 782-787. https://doi.org/10.1016/j.ifacol.2018.11.450
41. Лебедев П.Д., Казаков А.Л. Построение оптимальных покрытий выпуклых плоских фигур кругами различного радиуса // Труды Института математики и механики УрО РАН. 2019. Т. 25. № 2. С. 137-148. https://doi.org/10.21538/0134-4889-2019-25-2-137-148
42. Лебедев П.Д. Итерационные методы построения аппроксимаций оптимальных покрытий невыпуклых плоских множеств// Челябинский физико-математический журнал. 2019. Т. 4. № 1. С. 5-17. https://doi.org/10.24411/2500-0101-2019-14101
43. Preparata F.P., Shamos M.I.Computational geometry: An introduction. New York: Springer, 1985. https://doi.org/10.1007/978-1-4612-1098-6
44. Казаков А.Л., Лебедев П.Д. Алгоритмы построения наилучших $n$-сетей в метрических пространствах // Автоматика и телемеханика. 2017. Вып. 7. С. 141-155. http://mi.mathnet.ru/at14837
45. Лебедев П.Д. Программа вычисления оптимального покрытия полусферы набором сферических сегментов. Свидетельство о государственной регистрации № 2015661543 от 29.10.2015.
Поступила в редакцию
2022-07-18
Опубликована 2022-11-20
Опубликована 2022-11-20