Abstract
We study optimal approximations of sets in various metric spaces with sets of balls of equal radius. We consider an Euclidean plane, a sphere, and a plane with a special non-uniform metric. The main component in our constructions of coverings are optimal Chebyshev n-networks and their generalizations. We propose algorithms for constructing optimal coverings based on partitioning a given set into subsets and finding their Chebyshev centers in the Euclidean metric and their counterparts in non-Euclidean ones. Our results have both theoretical and practical value and can be used to solve problems arising in security, communication, and infrastructural logistics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Preparata, F. and Shamos, M., Computational Geometry, New York: Springer-Verlag, 1985. Translated under the title Vychislitel’naya geometriya, Moscow: Mir, 1989.
Zikratova, I.A., Shago, F.N., Gurtov, A.V., and Ivaninskaya, I.I., Optimizing the Coverage Zone for Cellular Network based on Mathematical Programming, Nauchn.-Tekhn. Vestn. Inform. Tekhnol., Mekh. Optiki, 2015, vol. 15, no. 2, pp. 313–321.
Geniatulin, K.A. and Nosov, V.I., Using the Method of Coordinating Rings for Frequency–Territorial Planning of a Satellite Communication System with Zonal Servicing, Vestn. SibGUTI, 2014, no. 1, pp. 35–45.
Bychkov, I.V., Kazakov, A.L., Lempert, A.A., et al., An Intelligent Control System for the Development of Transportational and Logistical Infrastructure of a Region, Probl. Upravlen., 2014, vol. 1, pp. 27–35.
Guseinov, Kh.G., Moiseev, A.N., and Ushakov, V.N., The Approximation of Reachable Domains of Control Systems, Appl. Math. Mech., 1998, vol. 62, no. 2, pp. 169–175.
Garkavi, A.L., On the Existence of an Optimal Network and Best Diameter of a Set in a Banach Space, Usp. Mat. Nauk, 1960, vol. 15, no. 2, pp. 210–211.
Garkavi, A.L., On an Optimal Network and Optimal Section of a Set in a Normed Space, Izv. Akad. Nauk SSSR, Ser. Mat., 1962, vol. 26, no. 1, pp. 87–106.
Lebedev, P.D. and Ushakov, A.V., Approximating Sets on a Plane with Optimal Sets of Circles, Autom. Remote Control, 2012, vol. 73, no. 3, pp. 485–493.
Lebedev, P.D., Uspenskii, A.A., and Ushakov, V.N., Optimal Approximation Algorithms for Flat Sets by Unions of Circles, Vestn. UdGU, Mat. Mekh. Komput. Nauk., 2013, no. 4, pp. 88–99.
Ushakov, V.N., Lakhtin, A.S., and Lebedev, P.D., Optimizing the Hausdorff Distance Between Sets in a Euclidean Space, Proc. IMM UrO RAN, 2014, vol. 20, no. 3, pp. 291–308.
Kazakov, A.L. and Lempert, A.A., An Approach to Optimization in Transport Logistics, Autom. Remote Control, 2011, vol. 72, no. 7, pp. 1398–1404.
Kazakov, A.L., Lempert, A.A., and Bukharov, D.S., On Segmenting Logistical Zones for Servicing Continuously Developed Consumers, Autom. Remote Control, 2013, vol. 74, no. 6, pp. 968–977.
Hausdorff, F., Grundzüge der Mengelehre, Veit and Company: Leipzig, 1914. Translated under the title Teoriya mnozhestv, Moscow: ONTI, 1937; Moscow: KomKniga, 2006.
Wu, J. and Yang, S., Energy-Efficient Node Scheduling Models in Sensor Networks with Adjustable Ranges, Int. J. Found. Comput. Sci., 2005, no. 16 (1), pp. 3–17.
Desyatov, V.G., Proektirovanie sistem ob”ektov obshchestvennogo kompleksa promyshlennykh predpriyatii (Systems Design for Public Service Objects of Industrial Plants), Moscow: MARKhI, 1989.
Sosov, E.N., The Metric Space of All n-Networks of a Geodesic Space, Uch. Zap. Kazan. Gos. Univ., Ser. Fiz.-Mat. Nauk, 2009, vol. 15, no. 4, pp. 136–149.
Piyavskii, S.A., On Optimization of Networks, Izv. Akad. Nauk SSSR, Tekhn. Kibern., 1968, no. 1, pp. 68–80.
Krotov, V.F. and Piyavskii, S.A., Sufficient Optimality Conditions in Optimal Coverage Problems, Izv. Akad. Nauk SSSR, Tekhn. Kibern., 1968, no. 2, pp. 10–17.
Heppes, A. and Melissen, H., Covering a Rectangle with Equal Circles, Period. Math. Hungar., 1997, vol. 34, pp. 65–81.
Melissen, J.B.M. and Schuur, P.C., Covering a Rectangle with Six and Seven Circles, Discret. Appl. Math., 2000, vol. 99, pp. 149–156.
Nurmela, K.J. and Östergard, P.R.J., Covering a Square with up to 30 Equal Circles, Res. Rept. A62 Lab. Technol. Helsinki Univ., 2000. http://www.tcs.hut.fi/Publications/reports
Galiev, Sh.I. and Karpova, M.A., Optimization of Multiple Covering of a Bounded Set with Circles, Comput. Math. Math. Phys., 2010, vol. 50, no 4, pp. 721–732.
Bychkov, I.V., Maksimkin, N.N., Khozyainov, I.S., and Kiselev, L.V., On the Patrol Problem for the Boundary of an Aquatic Region Protected by a Group of Submarines, Techn. Problems of the World Ocean, Proc. 5th Russ. Conf., Vladivostok, 2013, pp. 424–429.
Galiev, Sh.I., Multiple Packings and Sphere Coverings, Diskret. Mat., 1996, vol. 8, no. 3, pp. 148–160.
Lempert, A.A., Kazakov, A.L., and Bukharov, D.S., Mathematical Model and Program System for Solving a Problem of Logistic Objects Placement, Autom. Remote Control, 2015, vol. 76, no 8, pp. 1463–1470.
Kazakov, A.L., Zhuravskaya, M.A., and Lempert, A.A., Segmentation Problems for Logistical Platforms under the Development of Regional Logistics, Transport Urala, 2010, no. 4, pp. 17–20.
Kazakov, A.L., Lempert, A.A., and Bukharov, D.S., On One Numerical Method for Solving Certain Optimization Problems Arising in Transportation Logistics, Vestn. IrGTU, 2011, no. 6(53), pp. 6–12.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.L. Kazakov, P.D. Lebedev, 2017, published in Avtomatika i Telemekhanika, 2017, No. 7, pp. 141–155.
Rights and permissions
About this article
Cite this article
Kazakov, A.L., Lebedev, P.D. Algorithms for constructing optimal n-networks in metric spaces. Autom Remote Control 78, 1290–1301 (2017). https://doi.org/10.1134/S0005117917070104
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0005117917070104