1. Science
  2. Publications
  3. Information Processing Systems
  4. 1(156)'2019
  5. A generalized mathematical model of the problems of covering the area by identical circles and its major implementations

A generalized mathematical model of the problems of covering the area by identical circles and its major implementations

O. Antoshkin, O. Pankratov
Annotations languages:

Description: There is a rapidly growing interest in an effective solution to the problems of optimal coverage of regions of arbitrary shape by circles at the present stage. This is due to the variety of practical applications, the difficult formalizability of the conditions of the problem and the lack of a common approach for its solution. The situation is complicated by the presence of technological limitations on the mutual position of the circles and the position of the circles relative to the region. Most of the approaches proposed in the literature are heuristic for the reasons listed above. This leads to the loss of optimal and locally optimal solutions. The efficiency of solving the problem decreases as a result. The available exact approaches are implemented for particular cases of the problem. Thus, it seems relevant to build an adequate mathematical model of the problem of covering with identical circles of an arbitrary area, whose implementation covers the main tasks of a circular covering that arises in practice. The problem of covering an arbitrary region with identical circles is considered in the paper. A generalized mathematical model of the circular coverage problem is constructed in the form of a nonsmooth optimization problem based on the formalization of the criteria for completeness of the coverage. The feasible region of the problem is described by a system of inequalities consisting of two subsystems. The first of them occurs when writing membership functions for the formation of coating conditions. The second, an additional system of inequalities, serves to take into account technological constraints and is written using phi-functions. The model is nonsmooth due to the minimax nature of some phi-functions and membership functions. The tools for generating a set of implementations of a generalized mathematical model have been developed, covering a wide class of applied problems, including such problems: minimizing the length of wires; minimizing the radius of the circles; minimizing the number of laps; adjusting invalid coverage and adjusting invalid sensor placement. An effective strategy for solving the problem is proposed, based on the combination of the multi-start method with a set of constraint generators and objective functions for the basic implementations of the generalized model.

Keywords: circular coverage, completeness criterion, phi-functions, membership functions, mathematical model, nonlinear optimization


1. Wang, B. (2011), Coverage problems in sensor networks: A survey, ACM Comput. Surv, 43, pp. 1-56.
2. Stoyan, Yu.G. and Patcuk, B.H. (2006), “Pokrytie mnogougol'noj oblasti minimal'nym kolichestvom odinakovyh krugov zadannogo radiusa” [Covering a polygonal area with a minimum number of identical circles of a given radius], Reports of the National Academy of Sciences of Ukraine, No. 3, pp. 74-77.
3. Tarnai, T. and Gaspar, Zs. (1995), Covering a square by equal circles, Elem. Math., Vol. 50, pp. 167-170.
4. Brusov, B.C. and Piyavskij, S.A. (1971), “Vychislitel'nyj algoritm optimal'nogo pokrytiya oblastej ploskosti” [Computational algorithm for optimal coverage of plane areas], Journal of Computational Mathematics and Mathematical Physics, No. 2 (11), pp. 304-312.
5. Kiseleva, E.M., Lozovskaya, L.I. and Timoshenko, E.V. (2009), “Reshenie nepreryvnyh zadach optimal'nogo pokrytiya sharami s ispol'zovaniem teorii optimal'nogo razbieniya mnozhestv” [Solving continuous problems of optimal ball coverage using the theory of optimal partitioning of sets], Cybernetics and Systems Analysis, No. 3, pp. 98-117.
6. Ushakov, V.N. and Lebedev, P.D. (2016), “Algoritmy optimal'nogo pokrytiya mnozhestv na ploskosti ” [Algorithms for optimal coverage of sets on the plane in ], Vestn. Udmurtsk. in-ta. Matem. Mekh. Komp'yut. nauki, No. 3 (26), pp. 258-270.
7. Komyak, V., Pankratov, A., Patsuk, V. and Prikhodko, A. (2016), The problem of covering the fields by the circles in the task of optimization of observation points for ground video monitoring systems of forest fires, An international quarterly journal, No. 2 (5), pp. 133-138.
8. Antoshkin, O. and Pankratov, A. (2016), Construction of optimal wire sensor network for the area of complex shape, Eastern-European Journal of Enterprise Technologies, No. 6(4), pp. 45-53.
9. Ukrahrbudinform (2014), “Systemy protypozhezhnoho zakhystu: DBN V.2.5–56–2014, Chynnyi vid 2015-07-01” [Fire protection systems: DBN V.2.5-56-2014, Effective from 2015-07-01], Kyiv, 127 p.
10. Derzhspozhyvstandart of Ukraine (2009), “Systemy pozhezhnoi syhnalizatsii ta opovishchuvannia. Chastyna 14. Nastanovy shchodo pobudovy, proektuvannia, montuvannia, vvedennia v ekspluatatsiiu, ekspluatuvannia i tekhnichnoho obsluhovuvannia (CEN/TS 54-14:2004, IDT): DSTU-N CEN/TS 54-14:2009, Chynnyi vid 2010-01-01” [Fire alarm and warning systems. Part 14. Guidelines for the construction, design, installation, commissioning, operation and maintenance (CEN / TS 54-14: 2004, IDT): DSTU-N CEN / TS 54-14, Effective from 01/01/2010], Kyiv, 68 p.

 Antoshkin, O.A. and Pankratov, O.V. (2019), “Uzahalnena matematychna model zadachi pokryttia oblasti identychnymy kolamy ta yii osnovni realizatsii” [A generalized mathematical model of the problems of covering the area by identical circles and its major implementations], Information Processing Systems, Vol. 1(156), pp. 44-49. https://doi.org/10.30748/soi.2019.156.06.