Coverings of sets and domains by a system of circles whose centers have restrictions on their arrangement are considered. From the sensorrelated perspective, this corresponds to the sensor coverage problem, where the network sensors control objects or a region of space, but are located outside the control area. Formalizing the problem, we arrive at the problem of discrete geometry to determine the optimal number of circles, their sizes and locations, which provide the minimum coverage density of a given set. New results for the optimal outer covering of a circle, a square and a regular triangle are presented. The study of these models opens a possibility of building a sensor network with a minimal energy consumption.
Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. many more. WSN with restrictions on sensors location usually imply their location outside the control area. Therefore, in such studies the problem of effective external monitoring or the problem of external coverage is very topical. We considered this problem for an infinite strip on the plane [Erzin & Astrakov, 2013], where the boundary features of the circles cover arrangement were strictly taken into account. In this paper we consider deterministic models of finite sets coverings and domains with restrictions on the locations of circles centers. The obtained results not only have a useful sensory interpretation, but they also appear to be interesting geometric statements. In particular, the proofs of theorems on the optimal outer covering of a circle, a square and a regular triangle are presented in this paper. In connection with this one can recall the classical Holberg-Markus theorem on the minimal covering of a convex domain D on a plane by figures similar to D, but having a smaller dimension [Yaglom, 1971] and the problem of covering a square with a certain number of identical circles [Melisen & Schuur, 1996, Tarnai & G´asp´ar, 1995]. 2
Let G be a convex bounded domain of plane E2, and let Int G - the interior points of the domain, D - a subset of domain G. For a system of circles C(n) = fC1; C2; : : : ; Cng having centers A1; A2; : : : ; An and areas S1; S2; : : : ; Sn, we introduce the notations: U C(n) - the union of circles system, SC(n) - the total area of all circles from C(n). We formulate the following two optimization problems.
(G-D-n) Problem. Define for a given number n a system of circles C(n) satisfying the following conditions: D
U C(n); Ai 2 E2nInt G; i = 1; 2; : : : ; n; SC(n) ! min: (G-D) Problem. Find the number n for which the solution of the (G-D-n) Problem defines a system of circles with a minimal SC(n) value.
Next, we will use a brief notation for problems P(G-D-n) and P(G-D). We note that the formulated problems give rise to a number of specific problems, which are determined by the shape of region G and the type of set D. An important class of problems is given by condition D = G (designation P(G-G)). In general, D can be a discrete set of points, a set of lines, a subregion, or any other subset of G. The requirement of convexity of domain G makes the task more predictable and meaningful. Even for simple areas (a circle or a square) P(G-G) is very difficult, because the number of circles, their sizes and the specific position of the centers are unknown in advance. Probably, some individual problems can be solved by numerical methods by means of creating and implementing an appropriate algorithm.
The problem has a special meaning when set D is at some distance from boundary G. In this case it is possible to guarantee the existence of a minimal coverage area with a limited number of circles, since each “useful” circle should have a radius not less than some positive value. Moreover, for some figures, it is possible to infinitely “improve” the covering by a countable sequence of circles whose radius tends to zero. 3
Lemma 1. Let A and B be different points on plane E2. Then points M satisfy the condition jAM j2 + jBM j2 = d2 = const; (1) form a circle.
Lemma 1 provides the obvious statement.
Proposition 1. Let G be a circle of radius R. Then the solution of P(G-G-n), when n = 1 and n = 2, specifies the same minimum SC(n) = 4S(G) = 4 R2.
To prove Proposition 1, we must consider circles with centers at the points A and B lying at the ends of the same diameter of circle G. The circles radii R1 = jAM j and R2 = jBM j must satisfy condition (1) for d = jABj = 2R. If M = B, we get R2 = 0 that corresponds to the case n = 1.
Lemma 2. Let G be a circle and G - its boundary. Consider three different points A1, A2, A3 that are located arbitrarily on boundary G. We construct circles C1, C2, C3 with their centers in the middle of the corresponding arcs !1 = L(A1; A2), !2 = L(A2; A3), !3 = L(A3; A1) which minimize the cover of these arcs. Then these circles completely cover the circle and have a single common point inside circle G.
In other words, the outer covering of the boundary by three circles with their centers on this boundary provides a coverage of the entire circle. The covering of the boundary by four or more circles no longer possesses a similar property.
Lemma 3. Let fC1; C2g be the minimal outer covering of one arc !1 = L(A1; A2) of boundary circles. Then the circles have the same radius.
G by two
Proposition 2. Let G be a circle and D = G is a circle boundary. Then the solution of P(G-D-3) is also a solution of P(G-G-3) and they are realized with the help of three identical circles having the original circle size.
Note that the solution of P(G-G) for a circle is provided simultaneously by the solution of P(G-G-3) and P(G-G-4). More precisely, there is the following important result.
Theorem 1. Let G be a circle of radius R, S(G) - its area. Then the solution of the problem P (G-G) determines min SC(n) = 3S(G) = 3 R2. This minimum is reached in the case of n = 3 and n = 4.
When n = 3, cover C(n) satisfies the condition of Theorem 1 and represents three identical circles. Therefore, the covering density is 3. When n = 4, there is a class of optimal solutions. It is defined as follows: the radii of two large circles with their centers at the ends of the same diameter satisfy relation R12 + R22 = 5R2=2. Large circles cover most of the area including the central circle of radius 0; 5R. The radii of two small circles are equal to 0; 5R. They cover curvilinear triangles, “rolling” to the points of a boundary intersection of two big circles. Taking into account Lemma 1, the total area of two large circles of the cover does not change as their position changes. The symmetrical position of the cover circles is shown in Figure 1, and the extreme position of the cover circles, which can be accurately calculated, is shown in Figure 2.
Theorem 3. Let G be a regular triangle with a side a, S(G) – its area. Then the solution of P(G-G-3) determines the covering C(3) with min SC(3) = 7 1p63 S(G) 2; 3805S(G).
On the one hand, the outer covering with three circles, which satisfies Theorem 3, is shown in Figure 4. The circles radii are equal: 0; 5a, 0; 25a and 0; 125a, respectively. It is proved that three circles have a single common point inside the triangle. It can be assumed that this covering optimally covers the boundary of the triangle with three circles, since there are no points (except for the three adjacent ones) covered twice.
On the other hand, numerical calculations have shown that, by increasing the number of circles, the triangle covering density can be reduced (Figure 5). In this case SC(6) 2; 301S(G). This is because the angles of the triangle are sharp. We can also add additional circles for the last cover to improve the density.
Note that the domain covering density is not the only target. A cover with a large number of circles per one elementary area is difficult to implement in the sensor networks design. Therefore, the covering complexity level of the sensor network will be determined by the cost of installing sensors and energy consumption. 4
Let D (k) be a set of k points from G and C(n) - the minimal outer covering of D (k) (the optimal solution P(G-D*)). We can ask the following natural question.
Q1. How should we place the set of points D (k) in G so that the total covering area of SC(n) is maximal? A similar problem can be formulated for any subset D of G.
Q2. What is the way to put the set D (that is congruent to D) in G so that the minimum value SC(n) of the total cover area of D is maximal?
Note that, when we solve the max-min problem, the number of cover circles is not known in advance. Therefore, the search and justification of the solution (even for two and three points located in a circle or in a square) is rather complicated. If k is more than three, we will most likely have to limit ourselves to finding covers with a record density. When we consider Q1, it can be shown that the cover circles number does not exceed k. It is clear that the max-min problem can have an optimal solution realized on different covers, as in Theorem 2.
Here we represent the generalized max-min problem which includes the above questions.
Max-min (G-D*) Problem (MP(G-D* )). Let D = fD1; D2; :::; Dkg be a family of subsets each of which is contained in a given bounded convex domain G. For each i = 1; 2; : : : ; k we denote the subsets that are congruent to Di by Di . We need to determine the way in which the family of congruent subsets D = fD1 ; D2 ; : : : ; Dkg is located in G if the minimal total cover area SC(n) is maximal. The brief formal writing of the problem is as follows:
M P (G
D ) : max (min SC(n)):
D G C(n)
Proposition 3. Let G be a circle. The max-min outer covering problem MP(G-D*(k)) G has the following solutions for k = 1; 2; 3: (1) k = 1; point P1 is located in the center of circle G; SC(1) = S(G). (2) k = 2; two points P1, P2 are located symmetrically on one diameter of circle G at a distance d = (2 p3)R from the center; SC(1) = SC(2) = 4(2 p3)S(G) 1; 0718S(G).
(3) k = 3; point P1 is located in the center of circle G, points P2, P3 are located symmetrically on one diameter of circle G at a distance d = 0; 5R from the center; SC(1) = SC(2) = 1; 25S(G).
We can give a similar statement to square G. For k > 3 the problem MP(G-D*(k)) for the circle and the square remains unresolved. In this regard, we note that, for a large number of points, their location should be fairly uniform, and the total cover area SC(n) will necessarily be limited. According to Theorem 2, SC(n) < 3S(G).
For illustrative purposes, we give one more simple problem which solution is not obvious.
Problem. Let G be a circle of radius R, and let D be an arbitrary circle of radius r belonging to G. It is necessary to solve the problem MP(G-D*) for all r satisfying condition r < R.
This problem is interesting in the fact that, for a small value of r, the task is trivial (similar to a one-point problem). With increasing value r it is necessary to circumvent significant difficulties. Even the assumption that D lies in the center of circle G requires a profound argumentation. 5
The geometric problems about outer circular coverings of domains are natural and seem to be quite promising from the view point of possible practical applications. In our opinion, similar studies have also a purely scientific interest. Despite the fact that the tasks are formulated simply and clearly, their solutions require significant efforts. Moreover, only a small part of the formulated problems has been solved. We may formulate some new research topics which are, in some sense, the generalizations of our investigation.
(1) It is possible to consider the classes of coverings of a domain G by circles that “cling” to the boundary of a domain in a certain way (at least one point or "-neighborhood).
(2) We may consider the problem of packing figures of a given type into an area where each figure has a nonempty intersection with the domain boundary.
(3) Instead of one domain G on a plane, we can consider a regular structure from such areas (for example, their packing). Further, we may put the requirement for constructing a minimal coverage of this structure by circles whose centers are not contained in this structure.
Acknowledgements This work was supported by the Russian Foundation for Basic Research, Project 16-07-00552.