C&SA | Contents

Volume 58 >>> № 4 JULY — AUGUST 2022

-->

UDC 519.85

Yu. Stoyan¹, T. Romanova², O. Pankratov³, A. Tevyashev⁴

¹ A. Pidgorny Institute of Mechanical Engineering Problems, National Academy of Sciences of Ukraine, Kharkiv, Ukraine

yustoyan19@gmail.com

² A. Pidgorny Institute of Mechanical Engineering Problems, National Academy of Sciences of Ukraine, Kharkiv, Ukraine

tarom27@yahoo.com

³ A. Pidgorny Institute of Mechanical Engineering Problems, National Academy of Sciences of Ukraine, Kharkiv, Ukraine

pankratov2001@yahoo.com

⁴ Kharkiv National University of Radio Electronics, Kharkiv, Ukraine

andrew.teviashev@nure.ua

LATTICE COVERAGE OF CUBOID WITH MINIMUM NUMBER OF SEMISPHERES

Abstract. The problem of partial lattice coverage of a cuboid of given dimensions with a minimum number of identical hemispheres with a given coverage factor is considered. A mathematical model in the form of a mixed integer nonlinear programming problem is constructed. A solution algorithm is proposed. The problem of three-dimensional coverage is reduced to the problem of covering a rectangular area by a family of identical circles of radius that depends on the height of the cuboid, the radius of the hemispheres, and the distance between the centers of neighboring hemispheres. The results of computational experiments for the problem of optimizing the placement of sensors in a given three-dimensional domain are provided.

Keywords: hemispheres, lattice coverage, cuboid, mathematical model, optimization.

FULL TEXT

REFERENCES

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.

Feyesh Tot L. Arrangements on a plane, on a sphere and in space [Russian translation]. Moscow: Fizmatgiz, 1958. 363 p.

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.

Pankratov A.V., Patsuk V.N., Romanova T.E. A method for covering a rectangle with congruent circles, subject to additional constraints. Radioelektronika i informatika. 2005. N 1. P. 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.

Sergienko I.V., Stetsyuk P.I. About three scientific ideas of N.Z. Shora. Kibernetika i sistemnyj analiz. 2012. Vol. 48, N 1. P. 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.

Stetsyuk P.I. Theory and software implementations of Shor's r-algorithms. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 5. P. 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.