УДК 519.85
Ю.Г. СТОЯН,
Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, Україна,
yustoyan19@gmail.com
Т.Є. РОМАНОВА,
Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, Україна,
tarom27@yahoo.com
О.В. ПАНКРАТОВ,
Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, Україна,
pankratov2001@yahoo.com
А.Д. ТЕВЯШЕВ,
Харківський національний університет радіоелектроніки, Харків, Україна,
andrew.teviashev@nure.ua
РЕШІТЧАСТЕ ПОКРИТТЯ КУБОЇДА
МІНІМАЛЬНОЮ КІЛЬКІСТЮ ПІВCФЕР
Анотація. Розглянуто задачу часткового решітчастого покриття кубоїда заданих розмірів мінімальною кількістю однакових півсфер із заданим коефіцієнтом покриття. Побудовано математичну модель у вигляді задачі змішаного цілочислового нелінійного програмування. Запропоновано метод розв’язання, в якому застосовано ідею релаксації задачі тривимірного покриття до задачі покриття прямокутної області сім’єю однакових кругів радіуса, що залежить від висоти кубоїда, радіуса півсфер та відстані між центрами сусідніх півсфер. Наведено результати обчислювальних експериментів для прикладної задачі оптимізації розміщення сенсорів у заданій тривимірній області.
Ключові слова: півсфера, решітчасте покриття, кубоїд, математична модель, оптимізація.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Tevyashev A., Shostko I., Neofitnyi M., Koliadin A. Laser opto-electronic airspace monitoring system in the visible and infrared ranges. Proc. 2019 IEEE 5th International Conference Actual Problems of Unmanned Aerial Vehicles Developments (APUAVD 2019) (22–24 October 2019, Kyiv, Ukraine). Kyiv, 2019. P. 170–173.
- Shostko I., Tevyashev A., Neofitnyi M., Kulia Y. Information-measuring system of polygon based on wireless sensor infocommunication network. In: Data-Centric Business and Applications. Lecture Notes on Data Engineering and Communications Technologies. Radivilova T., Ageyev D., Kryvinska N. (Eds.). 2021. Vol. 48. P. 649–674. https://doi.org/10.1007/978-3-030-43070-2_8.
- Shostko I., Tevyashev A., Kulia Y., Koliadin A. Optical-electronic system of automatic detection and high-precise tracking of aerial objects in real-time. Proc. 3rd Interbatiobal Workshop on Computer Modeling and Intelligent Systems (CMIS-2020) (27 April – 1 May 2020, Zaporizhzhia, Ukraine). Zaporizhzhia, 2020. P. 784–803.
- Фейеш Тот Л. Расположения на плоскости, на сфере и в пространстве. Москва: Физматгиз, 1958. 363 с.
- Grinde R., Daniels K. Solving an apparel trim placement problem using a maximum cover problem approach. IIE Transactions. 1999. Vol. 31, Iss. 8. P. 763–769.
- Stoyan Y.G., Romanova T., Scheithauer G., Krivulya A. Covering a polygonal region by rectangles. Computational Optimization and Applications. 2011. Vol. 48. P. 675–695. https://doi.org/10.1007/s10589-009-9258-1.
- Tedeschi D., Andretta M. New exact algorithms for planar maximum covering location by ellipses problems. European Journal of Operational Research. 2021. Vol. 291, Iss. 1. P. 114–127. https://doi.org/10.1016/j.ejor.2020.09.029.
- Bansal M., Kianfar K. Planar maximum coverage location problem with partial coverage and rectangular demand and service zones. INFORMS Journal on Computing. 2017. Vol. 29, N 1. P. 152–169.
- Blyuss O., Zaikin A., Cherepanova V., Munblit D., Kiseleva E.M., Prytomanova O.M., Duffy S.W., Crnogorac-Jurcevic T. Development of PancRISK, a urine biomarker-based risk score for stratified screening of pancreatic cancer patients. British Journal of Cancer. 2020. Vol. 122, Iss. 5. P. 692–696. https://doi.org/10.1038/s41416-019-0694-0.
- Blyuss O., Koriashkina L., Kiseleva E., Molchanov R. Optimal placement of irradiation sources in the planning of radiotherapy: mathematical models and methods of solving. Computational and Mathematical Methods in Medicine. 2015. 142987. https://doi.org/10.1155/2015/142987.
- Stoyan Y., Patsuk V. Covering a compact polygonal set by identical circles. Computational Optimization and Applications. 2010. Vol. 46, Iss. 1. P. 75–92. https://doi.org/10.1007/s10589-008-9191-8.
- Stoyan Yu.G., Patsuk V.M. Covering a convex 3D polytope by a minimal number of congruent spheres. International Journal of Computer Mathematics. 2014. Vol. 91, Iss. 9. P. 2010–2020. https://doi.org/10.1080/00207160.2013.865726.
- Yakovlev S.V. On a class of problems on covering of a bounded set. Acta Mathematica Hungarica. 1989. Vol. 53, Iss. 3. P. 253–262, https://doi.org/10.1007/BF01953365.
- Shekhovtsov S.B., Yakovlev S.V. Formalization and solution of one class of covering problem in design of control and monitoring systems. Avtomatika i Telemekhanika. 1989. Iss. 5. P. 160–168, URL: http://mi.mathnet.ru/eng/at6296.
- Yakovlev S., Kartashov O., Komyak V., Shekhovtsov S., Sobol O., Yakovleva I. Modeling and simulation of coverage problem in geometric design systems. Proc. 2019 IEEE 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM) (26 February – 2 March 2019, Polyana-Svalyava, Ukraine). Polyana-Svalyava, 2019. P. 20–23. https://doi.org/10.1109/CADSM.2019.8779303.
- Панкратов А.В., Пацук В.Н., Романова Т.Е. Метод покрытия прямоугольника конгруэнтными кругами с учётом дополнительных ограничений. Радиоэлектроника и информатика. 2005. № 1. С. 54–58.
- Pankratov A., Romanova T., Litvinchev I., Marmolejo J.A. An optimized covering spheroids by spheres. Applied Sciences. 2020. Vol. 10, Iss. 5. 1846. https://doi.org/10.3390/app10051846.
- Fowler R., Paterson M., Tanimoto S. Optimal packing and covering in the plane are NP-complete. Information Processing Letters. 1981. Vol. 12, Iss. 3. P. 133–137.
- Pankratov A., Romanova T., Litvinchev I. Packing ellipses in an optimized convex polygon. Journal of Global Optimization. 2019. Vol. 75(2). P. 495–522.
- Stoyan Y.G., Romanova T.E., Pankratov O.V., Stetsyuk P.I., Maximov S.V. Sparse balanced layout of ellipsoids. Cybernetics and Systems Analysis. 2021. Vol. 57, N 6. P. 864–873. https://doi.org/10.1007/s10559-021-00412-3.
- Grebennik I.V., Kovalenko A.A., Romanova T.E., Urniaieva I.A., Shekhovtsov S.B. Combinatorial configurations in balance layout optimization problems. Cybernetics and Systems Analysis. 2018. Vol. 54, N 2. P. 221–231. https://doi.org/10.1007/s10559-018-0023-2.
- Сергиенко И.В., Стецюк П.И. О трех научных идеях Н.З. Шора. Кибернетика и системный анализ. 2012. Т. 48, № 1. C. 4–22.
- Stetsyuk P.I. Shor’s r-algorithms: theory and practice. In: Optimization Methods and Applications: In Honor of the 80th Birthday of Ivan V. Sergienko. Butenko S., Pardalos P.M., Shylo V. (Eds.). Springer International Publishing, 2017. P. 495–520.
- Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. Т. 53, № 5. С. 43–57.
- Wang B. Coverage problems in sensor networks: A survey. ACM Computing Surveys. 2011. Vol. 43, Iss. 4. P. 1–53.
- Kershner R. The number of circles covering a set. American Journal of Mathematics. 1939. Vol. 61, N 3. P. 665–671.
- Wang Y.C., Hu C.C., Tseng Y.C. Efficient deployment algorithms for ensuring coverage and connectivity of wireless sensor networks. Proc. 1st IEEE International Conference on Wireless Internet (WICON 2005) (10–15 July 2005, Budapest, Hungary). Budapest, 2005. P. 114–121.
- Stoyan Y., Pankratov A., Romanova T., Fasano J., Pinter T., Stoian Y.E., Chugay A. Optimized packings in space engineering applications. Part I. In: Modeling and Optimization in Space Engineering. Springer Optimization and Its Applications. Fasano G., PintБr J. (Eds.). Cham: Springer, 2019. Vol. 144. P. 395–437. https://doi.org/10.1007/978-3-030-10501-3_15.
- Stoyan Yu., Pankratov A., Romanova T. Placement problems for irregular objects: mathematical modeling, optimization and applications. In: Springer Optimization and Its Applications. Optimization Methods and Applications. Butenko S., Pardalos P., Shylo V. (Eds.). 2017. Vol. 130. P. 521–559. https://doi.org/10.1007/978-3-319-68640-0_25.