Back
 JAMP  Vol.8 No.10 , October 2020
Some Properties of the Sum and Geometric Differences of Minkowski
Abstract: The sets of Minkowski algebraic sum and geometric difference are considered. The purpose of the research in this paper is to apply the properties of Minkowski sum and geometric difference to fractional differential games. This paper investigates the geometric properties of the Minkowski algebraic sum and the geometric difference of sets. Various examples are considered that calculate the geometric differences of sets. The results of the research are presented and proved as a theorem. At the end of the article, the results were applied to fractional differential games.

1. Introduction

Minkowski sums and geometric differences are important operations. They are used in many fields, such as: image processing, robotics, computer-aided design, mathematical morphology and spatial planning. Minkowski sums and geometric differences are used in various fields of science, such as differential games and optimal control [1] [2] [3], computer-aided design and production [2], computer animation and morphing [3], morphological image analysis [4] [5], measures for convex polyhedral [6], dynamic modeling [7], robot motion planning [8] and so on.

If our activity in the study of vector algebra in ordinary space n begins with the addition of two vectors, then this activity extends to the addition of a vector or vectors belonging to one set to vectors belonging to another set. It is important to understand intuitively that adding a set to a vector is a combination of vectors formed by adding each element of the set to the vector [9] [10] [11]. For example, to add a set A to set B in a plane 2 , you need to copy the set A onto each element of the set B and get the combination, or vice versa. This process is not difficult to imagine, even in arbitrary of n dimensional space, and it can be seen that the geometric nature of the sets A and B does not depend on their location relatively to the origin [12] [13] [14] [15].

Minkowski operators were first used in the work of L.S. Pontryagin to study differential games. L.S. Pontyagin’s 1967 article “On linear differential games II” [16] provides definitions and several properties of the Minkovsky algebraic sum and the Minkovsky geometric difference.

Also, the application of Minkovsky’s operator to differential games is described by N.Yu. Satimov, G.E. Ivanov, B.N. Pshenichny. In a 1973 article by N.Yu. Satimov, a linear differential game in n-dimensional Euclidean space is considered. In this work, N.Yu. Satimov finds in the linear differential game a sufficient condition that ensures that the chaser finishes the game in real time in the action of any possible line of the runner and proves it in the form of a theorem. He used Minkowski’s difference and its properties to prove these theorems.

In the above work, the Minkowski sum and geometric difference are applied to whole-order differential games. In this article, we have tried to solve the following problems:

1) Identify and prove the important properties of the Minkowski sum and difference;

2) Minkowski sum and difference of open and closed sets;

3) Application of Minkowski’s sum and difference to fractional differential games.

2. Research Methodology

Definition 1. Let X , Y E be nonempty sets on the linear space E. The Minkowski sum and difference of two sets X and Y are defined to be the sets

X + Y = { x + y : x X , y Y } , X Y = { x E : x + Y X } . (1)

Definition 2. The multiplication of set X and number λ is defined to be the set

λ X = { λ x : x X } . (2)

Definition 3. The Minkowski sum of any vector a E and nonempty set X E is defined to be the set

a + X = { a + x : x X } (3)

By the definition of the Minkowski difference of sets, the set X Y means the intersection of movement of the set X to vector d Y , which is

X Y = d Y ( X + d ) (4)

To prove this equality, it’s enough to show all z X Y are belonged to set d Y ( X + d ) and on the contrary. By the definition of the muliplication of set and number, expression d Y means that always there exists y element in the set Y such that d = y . Hence y = d Y .

Let z X Y be vector of set X Y . Then by the definition of Minkowski difference of sets (4), z + Y X . By the definition of the Minkowski sum of sets, for all y Y elements there exists x X element such that z + y = x , z = x y . Since y = d , z = x + d . This equality is true for all d Y and such x X , so we can write following expressions

z X + d , z d Y ( X + d ) (5)

Therefore, if z X Y , then z d Y ( X + d ) .

Now, let z d Y ( X + d ) be vector of intersection d Y ( X + d ) , then z X + d for all d Y vectors. Hence there exists x X vector such that z = x + d . Then z = x + d = x y and z + y = x , since d = y . This equality is true for all y Y and such x X , so we can write z + Y X , hence z X Y . Therefore equality (4) is really true. In formula (4), the Minkovsky difference is expressed by the Minkovsky sum, which helps to visualize the Minkovsky difference.

Definition 4. Unit of all the boundary points of set X is called boundary of X and written X .

Definition 5. The complement of given set X on the linear space E is written X c and defined to be the set

X c = { x E , x X } . (6)

Definition 6. The Minkowski operators of the multiple-valued function G : E 2 E , written as A G : 2 E 2 E and B G : 2 E 2 E , are defined to be operators

A G S = x S ( x + G ( x ) ) , B G S = E \ ( A G ( E \ S ) ) (7)

in here S E be any set.

In especial condition multiple-valued function G is constant G ( x ) = G 0 for each x S , then Minkowski operators become as Minkowski sum and difference:

A G S = S + G 0 , B G S = S ( G 0 ) (8)

It is very important to know that, Minkowski sum and difference of the given sets are open or closed set. Therefore, we are writing following lemmas and theorems.

3. Analysis and Results

Lemma 1. Let X , Y E be nonempty sets on the linear space E and X Y . For any vectors y Y there exists a vector x X such that

x y X Y . (9)

Proof. Let a X Y , then by the definition of Minkowski difference a + Y X . By the definition of Minkowski sum of sets for each y Y there exists vector x X such a + y = x . Hence a = x y . Therefore, a = x y X Y relation is true.

Lemma 2. For any nonempty sets X and Y on the linear space E following relation is true:

X Y X + ( Y ) . (10)

Proof. To prove this lemma we show that every element of X Y will be an element of X + ( Y ) and on the contrary.

Let a X Y be any vector. By the definition of the Minkowski difference of sets we can write a + Y X . For all y Y vectors a + y X . We add y Y vector to both sides of this relation. Hence a X + ( y ) . Since X + ( y ) X + ( Y ) relation, follows that a X + ( Y ) . Following example shows that each a X + ( Y ) vector does not belong to X Y set every time. Let X = [ 4 , 5 ] ; Y = ( 3 , 4 ) be given sets. Then Y = ( 4 , 3 ) , X + ( Y ) = ( 8 , 2 ) , X Y = [ 7 , 1 ] . Therefore, X Y X + ( Y ) .

Lemma 3. For any nonempty sets X and Y on the linear space E following relation is true:

( X Y ) c = Y + X c (11)

Proof. Let a ( X Y ) c be any vector, then a X Y . By the definition of the Minkowski difference of sets a + Y X . There exists y Y vector such that a + y X c and there exists x X c vector such that a + y = x . Hence a = x y Y + X c , therefore a Y + X c .

Lemma 4. For any nonempty sets X and Y on the linear space E following relation is true:

λ ( X Y ) = λ X λ Y (12)

Proof. Let a λ ( X Y ) be any vector. By the definition of multiplication of sets and number there exists t X Y vector such that a = λ t . Since t X Y , we have t X and t Y . Hence, λ t λ X and λ t λ Y . It means that λ t λ X λ Y . We can show that every vector a λ X λ Y belongs to set λ ( X Y ) by using this method. Lemma has been proved.

Lemma 5. For any nonempty set X on the linear space E and for number λ following relation is true:

λ X = ( λ X ) (13)

in here X means boundary of the set X.

Proof. Let a λ X be a vector, there exists x X vector such that a = λ x . x X means that for all neighborhoods B r ( x ) = { x : x x < r , r R } of x B r ( x ) X , B r ( x ) X c . We multiply both sides of these relations by number λ and according to the lemma 4, we have B λ r ( λ x ) λ X , B λ r ( λ x ) ( λ X ) c . It means that a = λ x ( λ X ) . We can show that every vector a ( λ X ) belongs to set λ X by using this method (13). Lemma has been proved.

Lemma 6. For any nonempty sets A , B , C and D on the linear space E following relation is true:

( A B ) + ( C D ) ( A + C ) ( B + D ) (14)

Proof. Let x ( A B ) + ( C D ) be a vector. By the definition of Minkowski sum there exists t A B and k C D such that x = t + k . It means t A , t B , k C , k D . Hence, it follows t + k A + C and t + k B + D . Therefore, x = t + k ( A + C ) ( B + D ) . Following example shows that each x ( A + C ) ( B + D ) vector does not belong to ( A B ) + ( C D ) set every time (14). Let A = [ 1 , 2 ] , B = [ 3 , 4 ] , C = [ 7 , 8 ] , D = [ 5 , 6 ] be given sets. Then ( A B ) + ( C D ) = , ( A + C ) ( B + D ) = [ 8 , 10 ] [ 8 , 10 ] = [ 8 , 10 ] . Therefore ( A B ) + ( C D ) ( A + C ) ( B + D ) .

Lemma 7. Let X , Y E be nonempty sets on the linear space E. If X Y , then λ X λ Y .

Proof. From X Y there exists set Z such that Y = X Z . It means that each element y Y is an element of set X or an element of set Y or an element of both sets. This implies that for y Y there exists vector x X or vector z Z such that y = x or y = z . By the definition of liner space we multiply both sides of these equalities by number λ and it follows that λ y = λ x or λ y = λ z . Hence, λ y λ X or λ y λ Z . It means equality λ Y = λ X λ Z is true. Therefore, λ X λ Y .

Lemma 8. Let X 1 , X 2 , Y 1 , Y 2 be nonempty sets on the linear space E. If X 1 X 2 , Y 1 Y 2 , then X 1 + Y 1 X 2 + Y 2 .

Proof. Let a X 1 + Y 1 be any vector of set X 1 + Y 1 . By the definition of Minkowski sum of sets there exists x 1 X 1 and y 1 Y 1 such that a = x 1 + y 2 . Since X 1 X 2 , Y 1 Y 2 , we have x 1 X 2 and y 1 Y 2 . It means that x 1 + y 1 X 2 + Y 2 . Therefore a 1 X 2 + Y 2 . Lemma has been proved.

Lemma 9. Let X 1 , X 2 , Y 1 , Y 2 be nonempty sets on the linear space E. If X 1 X 2 , Y 1 Y 2 , then X 1 Y 1 X 2 Y 2 .

Proof. Let a X 1 Y 1 be any vector. By the definition of the Minkowski difference a + Y 1 X 1 . Since X 1 X 2 , it follows a + Y 1 X 1 X 2 , a + Y 1 X 2 .

According to the condition of the theorem, Y 2 Y 1 and by the lemma 8, a + Y 1 + Y 2 X 2 + Y 1 . Hence, a + Y 2 X 2 . Therefore, a X 2 Y 2 .

Lemma 10. For any nonempty sets X, Y and Z on the linear space E following relation is true:

X + ( Y Z ) X + Y Z (15)

Proof. Let a X + ( Y Z ) be any vector of set X + ( Y Z ) , then there exists x X and t Y Z such that a = x + t . Since t Y Z , we have t + Z Y . We add vector x X to both sides of these relations and we obtain x + t + Z x + Y X + Y . It means that a + Z X + Y . Hence, a X + Y Z .

Following example shows that each a X + Y Z vector does not belong to X + ( Y Z ) set every time. Let X = ( 0 , 4 ) ; Y = ( 3 , 5 ) ; Z = ( 2 , 1 ) be given sets. Then we obtain X + ( Y Z ) = ( 5 , 8 ) and X + Y Z = [ 5 , 8 ] . Therefore, X + ( Y Z ) X + Y Z .

Lemma 11. For any nonempty sets X, Y and Z on the linear space E following relation is true:

X + ( Y Z ) Y ( Z X ) (16)

Proof. Let a X + ( Y Z ) be any vector of the set X + ( Y Z ) , then by definition of the Minkowski sum, there exists vectors x X and t Y Z such that a = x + t , t = a x . Since t Y Z , t + Z Y . According to t Y Z , we have a x + Z Y . Thus, a + Z + ( X ) Y . By the lemma 2, we have Z X Z + ( X ) . Hence, a + ( Z X ) a + Z + ( X ) Y . Thus, a + ( Z X ) Y . Therefore, a Y ( Z X ) .

Following example shows that each vector a X + Y Z does not belong to set X + ( Y Z ) every time (15). Let X = ( 0 , 2 ) ; Y = [ 3 , 8 ] ; Z = ( 2 , 1 ) be given sets. Then X + ( Y Z ) = ( 5 , 9 ) and Y ( Z X ) = [ 5 , 9 ] . Therefore, X + ( Y Z ) Y ( Z X ) .

Lemma 12. For any nonempty set X on the liner space E following equality is true.

X c = ( X ) c (17)

Proof. Let a X c be any vector of the set X c . By the definition of multiplication of sets and numbers, there exists a X c . Thus, a X It means that for all x X , a x , a x . This implies a X . Consequently, a ( X ) c . We can show that every vector a ( X ) c belongs to set X c by using this method. Lemma has been proved.

Theorem 1. For any nonempty sets X, Y on the linear space E following equality is true:

Y ( Y X ) = X + ( Y ) c ( Y ) c (18)

Proof. Let a Y ( Y X ) be any vector. By the definition of the Minkowski difference of sets, a + ( Y X ) Y . It means that a + t Y for all vectors t Y X . Thus, a t Y and a t ( Y ) c . Then for all vectors ( y ) ( Y ) c following relations is true

a t ( y ) ,

a + ( y ) t ( Y X ) , (19)

a + ( y ) ( Y X ) .

From this and by the lemma 12, it follows that a + ( y ) ( Y X ) c . By the lemma 3, we can write following relations

a + ( y ) ( Y X ) c = ( X + Y c ) , a + ( Y ) c X Y c (20)

Since Y c ( Y ) c , we have a + ( Y ) c X + ( Y ) c , a X + ( Y ) c ( Y ) c .

We can show that every vector a X + ( Y ) c ( Y ) c belongs to set Y ( Y X ) by using this method (18). Lemma has been proved.

Theorem 2. For any nonempty sets X, Y and Z on the linear space E following relation is true:

( X Z ) ( Y Z ) = ( X Y ) Z (21)

Proof. Let a ( X Z ) ( Y Z ) be any vector of set ( X Z ) ( Y Z ) . By the definition of the intersection of sets, it follows that a X Z and a Y Z . By the definition of Minkowsli difference of sets, we have a + Z X and a + Z Y . From these, a + Z X Y , a ( X Y ) Z .

Now, let a ( X Y ) Z be any vector. Then by the definition of the Minkowski difference of sets, a + Z X Y . By the definition of intersection of sets, we have a + Z X and a + Z Y . Thus, a X Z and a Y Z . It means that a ( X Z ) ( Y Z ) . Therefore ( X Z ) ( Y Z ) = ( X Y ) Z . Theorem has been proved.

Theorem 3. For any sets X , Y E and any vector a E , following equality is true

( a + X ) ( a + Y ) = a + ( X Y ) . (22)

Proof. Let t ( a + X ) ( a + Y ) be any vector. By the definition of the union of sets, t ( a + X ) or t ( a + Y ) , or both relation will be true. By the definition of the Minkowski sum of sets, there exists x X or y Y such that t = a + x or t = a + y . Thus, t a = x or t a = y . These imply t a X or t a Y . It means that t a ( X Y ) . Therefore, t a + ( X Y ) .

We can show that every vector t a + ( X Y ) belongs to set ( a + X ) ( a + Y ) by using this method. Theorem has been proved.

Theorem 4. For any nonempty sets X, Y and Z on the linear space E following equality is true:

( X Y ) ( X Z ) = X ( Y Z ) . (23)

Proof. Let a ( X Y ) ( X Z ) be any vector of set ( X Y ) ( X Z ) . By the definition of the intersection of sets a X Y and a X Z . By the definition of the Minkowski difference of sets, a + Y X and a + Z X . Thus, ( a + Y ) ( a + Z ) X . According to the theorem 3,

( a + Y ) ( a + Z ) = a + ( Y Z ) X . (24)

Hence, a X ( Y Z ) .

We can show that every vector a X ( Y Z ) belongs to set ( X Y ) ( X Z ) by using this method. Theorem has been proved. Therefore equality ( X Y ) ( X Z ) = X ( Y Z ) is true (23).

Following theorems may be proved by using of the lemmas given above.

Theorem 5. If X be open (closed) set, then λ X will be open (closed) set too.

Proof. Suppose X be open set. Then for each x 0 X vectors there exists neighborhood B r ( x 0 ) = { x : x 0 x < r } such that B r ( x 0 ) X . It is multiplied both sides of this relation by the number λ , consequently B λ r ( λ x 0 ) λ X . In here B λ r ( λ x 0 ) = { x : λ x 0 x < λ r } . It means that all points of set λ X are interior points, therefore λ X is open set.

Now suppose X be closed set. By the definition of closed set for all x 0 X vectors there exists neighborhoods B r ( x 0 ) = { x : x 0 x < r } such that B r ( x 0 ) X . It is multiplied both sides of this relation by the number λ , consequently B λ r ( λ x 0 ) λ X . It means that all points of set the λ X are adherent points, therefore λ X is closed set.

Theorem 6. Let X , Y E be nonempty sets on the linear space E. If either of them is an open set, then X + Y will be an open set and in other conditions it will be a closed set.

Proof. According to the condition of the theorem, either of given sets must be open set. Suppose set X be open set. According to the definition of the open sets, for all x 0 X vectors there exists it’s neighborhood B r ( x 0 ) = { x : x 0 x < r } such that B r ( x 0 ) X . By the properties of Minkowski sum of the sets and according to the lemma 8 we can write following relation:

B r ( x 0 ) + y 0 X + Y (25)

in here y 0 is any vector of the set Y.

The neighborhood B r ( x 0 ) = { x : x 0 x < r } is open ball with center x 0 and radius r. By the definition of the Minkowski sum,

B r ( x 0 ) + y 0 = B r ( x 0 + y 0 ) (26)

In here the set B r ( x 0 + y 0 ) = { z : ( x 0 + y 0 ) z < r } is open ball with center ( x 0 + y 0 ) and radius r. Since (25) and (26), it follows B r ( x 0 + y 0 ) X + Y . Therefore, X + Y is open set. First part of theorem has been proved.

Now we must prove second part of theorem. Suppose both sets X , Y are closed. By the definition of closed sets, for all neighborhoods B r 1 ( x 0 ) = { x : x 0 x < r 2 } and B r 2 ( y 0 ) = { y : y 0 y < r 2 } of x 0 X and y 0 Y we can record B r 1 ( x 0 ) X , B r 2 ( y 0 ) Y . Hence, ( B r 1 ( x 0 ) X ) + ( B r 2 ( y 0 ) Y ) . According to the lemma 6, it follows ( B r 1 ( x 0 ) X ) + ( B r 2 ( y 0 ) Y ) ( B r 1 ( x 0 ) + B r 2 ( y 0 ) ) ( X + Y ) . By the Minkowski sum B r 1 ( x 0 ) + B r 2 ( y 0 ) = B r 1 + r 2 ( x 0 + y 0 ) , then relation becomes B r 1 + r 2 ( x 0 + y 0 ) ( X + Y ) . It means that X + Y is closed set. Theorem has been completely proved.

Theorem 7. Let X , Y E be nonempty sets on the linear space E. If the set X is open and the set Y is closed, then the set X Y will be the open one, and in other conditions it will be a closed set.

Proof. Suppose set X Y be closed. Then set ( X Y ) с will be an open set. By the lemma 3, ( X Y ) с = Y + X c . It means that, set Y + X c must be open. But according to the condition of theorem, set X is open and the set Y is closed so X c will be closed and according to the theorem 1, set Y will be closed too. By the theorem 2, set Y + X c will be closed. It means contradiction. Therefore, our suppose is not true and X Y will be open set.

4. The Discussion of the Results

In this section we give possible applications of the results of the previous paragraph.

4.1. Fractional Differential Games with Lumped Parameters

Let the motion of an object in a finite-dimensional Euclidean space R n is described by a differential equation of fractional order of the form

D 0 t α z = A z + B u G υ + f ( t ) (27)

where z R n , n 1 ; D 0 t α —fractional differentiation operator, α > 0 , t [ 0 , T ] , A—n × n, B—p × n and G—q × n constant matrices, u , υ —control parameters u—chasing player control parameter, u P R p , υ —runaway control parameter, υ Q R q , P and Q—compacts, f ( t ) —known measurable vector function. The fractional derivative will be understood as the left-side fractional derivative of Caputo [11]. Recall that the Caputo fractional derivative of an arbitrary non-target order α > 0 from function z ( t ) A C [ α ] + 1 ( 0 , b ) , b R 1 , defined by the expression

D 0 t α z ( t ) = 1 Γ ( 1 { α } ) 0 t d [ α ] + 1 z ( ξ ) d ξ [ α ] + 1 d ξ ( t ξ ) { α } (28)

Also in space R n terminal set is allocated M. Chasing player goal to deduce z to many M, the fleeing player seeks to prevent this.

We consider the pursuit problem of approximating the trajectory of a conflict-controlled system (27) with a terminal set M for a finite time from given initial positions z 0 . We say that the differential game (27) can be completed from the initial position z 0 during T = T ( z 0 ) , if there is such a measurable function u ( t ) = u ( z 0 , υ ( t ) ) P , t [ 0 , T ] , what’s the solution to the equation

D 0 t α z = A z + B u ( t ) G υ ( t ) + f ( t ) , z ( 0 ) = z 0 (29)

belongs to many M in the moment t = T for any measurable functions υ ( t ) , υ ( t ) Q , 0 t T .

Let us pass to the statement of the main results. Throughout what follows: 1) a terminal set M has the form M = M 0 + M 1 , where M 0 —linear subspace R n , M 1 —subset of subspace L—orthogonal additions M 0 ; 2) π —orthogonal projection operator from R n on L; 3) under operation * Minkowski geometric difference operation.

Let e α A t = t α 1 k = 0 A k t α k Γ ( ( k + 1 ) α ) -matrix α -exhibitor [11] and r 0 , u ^ ( r ) = π e α r A B P , υ ^ ( r ) = π e α r A G Q , w ^ ( r ) = u ^ ( r ) * υ ^ ( r ) ;

W ( τ ) = 0 τ w ^ ( r ) d r , τ > 0 , W 1 ( τ ) = M 1 + W ( τ ) (30)

In [12], it was proved that if in the game (27) for some τ = τ 1 , turning on

π z 0 0 τ π e α A ( τ r ) [ A z 0 + f ( r ) ] d r W 1 ( τ ) (31)

then from the starting position z 0 can complete the pursuit in time T = τ 1 .

4.2. Fractional Differential Games with Distributed Parameters

A controllable distributed system is described, described by equations of fractional order [11]

D 0 t α z = C x D 0 x β z + C y D 0 y β z u + υ , ( t , x , y ) Ω , (32)

z | t = 0 = 0 , ( x , y ) G ¯ , (33)

z | L = φ ( x , y ) , ( x , y ) G ¯ , (34)

where z-unknown function from class С 2 ( Ω ) , Ω = G × ( 0 , T ] , G = { 0 x 1 , 0 y 1 }

- rectangle with border L. t [ 0 , T ] , T—arbitrary positive constant; C x , C y —thermal conductivity coefficients; 0 < α 1 , 1 < β 2 ;

D 0 t α z ( t , x , y ) = t I 0 t 1 α , D 0 x β z ( t , x , y ) = ( x ) 2 I 0 x 2 β , D 0 y β z ( t , x , y ) = ( y ) 2 I 0 y 2 β

- partial fractional derivatives of Riemann-Liouville;

I 0 + α z ( t , x , y ) = 1 Γ ( α ) 0 t z ( s , x , y ) ( t s ) 1 α d s

- partial fractional Riemann-Liouville integrals with respect to the corresponding variable [11]. u , υ —control parameters u—chasing player control parameter, u P R , υ —runaway player control parameter, υ Q R , P and Q-compacts. Also in space R n terminal set is allocated M = M ¯ + ε S where ε > 0 , S = [ 1 , 1 ] . Chasing player goal to deduce z to many M, the fleeing player seeks to put it. A game is considered completed if z fall into M: z M .

Let be f ( x ) —some function with scope Ω . Then there is a finite-difference definition of the derivative of the order β R at the point x D ( f ) :

D a x β f = lim n + ( n x a ) β k = 0 n q k f ( x x a n k ) , (35)

where 1 < β 2 ; q 0 = 1 , q k = ( 1 ) k β ( β 1 ) ( β k + 1 ) / k ! . According to [11], if f C 2 ( Ω ) , then the Grunwald derivative coincides with the Riemann-Liouville derivative. To approximate fractional Riemann-Liouville derivatives with respect to variables x , y at 1 < β < 2 on the segment [ 0 , 1 ] , [ 0 , 1 ] we use the Grunwald-Letnikov formula with an offset:

D a x β f = lim n + 1 h β k = 0 [ x / h ] q k f ( x ( k 1 ) h ) , (36)

where h = x / M . Formula (36) provides a more accurate approximation than the standard Grunwald-Letnikov formula.

Using Formula (36), for derivatives of fractional Riemann-Liouville order with respect to spatial variables in the case 1 < β < 2 we get

D 0 x β z ( t , x , y ) | x n 1 h β j = 0 n + 1 q j z ( t , x n j + 1 , y ) , (37)

D 0 y β z ( t , x , y ) | y m 1 h β j = 0 m + 1 q j z ( t , x , y m j + 1 ) , (38)

here x n j + 1 x n ( j 1 ) h , y m j + 1 y m ( j 1 ) h .

Using a sufficient sign of the existence of a fractional derivative of the Riemann-Liouville 0 < α 1 , on the segment [ t k , t k + 1 ] we get

D 0 t α z ( t , x , y ) | t k = 1 Γ ( 1 α ) ( z ( t k , x , y ) ( t k + 1 t k ) α + t k t k + 1 z ( x , s ) d s ( t k + 1 s ) α ) , (39)

here

Γ ( α ) = 0 x α 1 e x d x (40)

Introducing the Derivative z ( τ , x , y ) on the segment [ t k , t k + 1 ] in the form of a finite difference

( d z d τ ) k z ( t k + 1 , x , y ) z ( t k , x , y ) τ , (41)

difference approximation of a fractional derivative α on the segment [ t k , t k + 1 ] can be written as

D 0 t α z ( t , x , y ) | t k 1 Γ ( 1 α ) ( z ( t k , x , y ) ( t k + 1 t k ) α + z ( t k + 1 , x , y ) z ( t k , x , y ) τ t k t k + 1 d s ( t k + 1 s ) α ) = z ( t k + 1 , x , y ) α z ( t k , x , y ) Γ ( 1 α ) ( 1 α ) τ α (42)

To find a solution to problem (32)-(34) in the region Ω ¯ = { ( x , y , t ) : 0 x 1 , 0 y 1 , 0 t T } introduce the grid

ϖ h x , h y , τ = { ( x n , y m , t k ) : x n = n h x , y m = m h y , t k = k τ ; n = 0 , 1 , , n 0 , h x = 1 / n 0 ; m = 0 , 1 , , m 0 , h y = 1 / m 0 ; k = 0 , 1 , , T / k 0 } (43)

in increments h x on x, h y on y and τ on t. Denote

z k , n , m z ( t k , x n , y m ) , z k , n j + 1 , m z ( t k , x n j + 1 , y m ) , z k , n , m j + 1 z ( t k , x n , y m j + 1 ) , u k , n , m u ( t k , x n , y m ) , υ k , n , m υ ( t k , x n , y m ) . (44)

Using equalities (35)-(40) for Equation (32), we write the explicit difference scheme

z k + 1 , n , m α z k , n , m Γ ( 2 α ) τ α = C x h x β ( z k , n + 1 , m β z k , n , m + j = 2 n + 1 q j z k , n j + 1 , m ) + C y h y β ( z k , n , m + 1 β z k , n , m + j = 2 m + 1 q j z k , n , m j + 1 ) u k , n , m + υ k , n , m . (45)

It is known that the difference scheme (45) is stable when

τ α ( C x h x β + C y h y β ) α + 1 ( 2 + β ) Γ ( 2 α ) ,

where 0 < α 1 , 1 < β 2 .

Decomposing functions z k + 1 , i + 1 , j , z k + 1 , i , j , z k , i , j , z k + 1 , i 1 , j , z k , i , j + 1 , z k , i , j 1 in the Taylor series and substituting the obtained relations in the difference scheme (45), we obtain

α z t α ( t k , x i , y j ) = C x β z x β ( t k , x i , y j ) + C y β z y β ( t k , x i , y j ) u k , i , j + υ k , i , j + a ( τ 2 α ) + b ( h x 2 ) + c ( h y 2 ) , (46)

where a , b , c —some constants. Therefore, the difference scheme (45) approximates Equation (32) with the order 2 α in time and second order in coordinates x , y .

In the case of a square grid, i.e. when h x = h y = h , C x = C y = C , for difference scheme (45) we have

z k + 1 , n , m = ( α 2 γ β ) z k , n , m + γ ( z k , n + 1 , m + j = 2 n + 1 q j z k , n j + 1 , m + z k , n , m + 1 + j = 2 m + 1 q j z k , n , m j + 1 ) + Γ ( 2 α ) τ α ( u k , n , m + υ k , n , m ) , (47)

z k , 0 , m = φ ( 0 , y m ) , z k , N , m = φ ( 1 , y m ) , z k , n , 0 = φ ( x n , 0 ) , z k , n , M = φ ( x n , 1 ) , z 0 , n , m = 0 , (48)

where γ = Γ ( 2 α ) τ α С / h β .

The difference scheme (48) is stable when

τ α ( α + 1 ) h β ( 2 + β ) Γ ( 2 α ) С , (49)

where 0 < α 1 , 1 < β 2 .

Now for the convenience of presentation, we write problem (47), (48) in matrix form

z k + 1 = A k z k l u k + l υ k , k = 0 , 1 , 2 , , θ 1 , z 0 = φ ¯ , (50)

where z k , u k , υ k —H-dimensional matrices, H—the total number of nodes belonging to one layer, i.e. given t = k τ , where in

z k = ( z k , 1 , 1 , z k , 1 , 2 , , z k , 1 , r 1 , , z k , i , j , , z k , r 1 , r 1 ) T , u k = ( u k , 1 , 1 , u k , 1 , 2 , , u k , 1 , r 1 , , u k , i , j , , u k , r 1 , r 1 ) T , υ k = ( υ k , 1 , 1 , υ k , 1 , 2 , , υ k , 1 , r 1 , , υ k , i , j , , υ k , r 1 , r 1 ) T , (51)

respectively,

φ ¯ = ( φ ( h , h ) , φ ( h , 2 h ) , , φ ( h , ( r 1 ) h ) , , φ ( i h , j h ) , , φ ( ( r 1 ) h , ( r 1 ) h ) ) T (52)

initial vector, n ( r 1 ) = H , A k —H-dimensional square matrix.

Let in R H terminal set is allocated M. We say that in the game (47), (48) from the point z 0 = f ¯ R H \ M can complete the persecution for N θ steps, if by any sequence υ ¯ 0 , υ ¯ 1 , , υ ¯ N 1 runaway control can build such a sequence u ¯ 0 , u ¯ 1 , , u ¯ N 1 management prosecution that decision ( z ¯ 0 , z ¯ 1 , , z ¯ N 1 ) equations z k + 1 = A k z k l u ¯ k + l υ ¯ k , k = 0 , 1 , , N 1 , for some d N gets on M : z ¯ d M .

Suppose that in game (50) the terminal set has the form M = M 0 + M 1 , where M 0 ( H γ ) -dimensional linear subspace R H , M 1 —subset of subspace L—orthogonal additions M 0 in R H . Next, through Π denote the orthogonal projection matrix from R H on L, and through A + B and A * B algebraic sum and geometric difference of Minkowski sets A , B respectively. Let be

P = P ¯ × P ¯ × × P ¯ H , Q = Q ¯ × Q ¯ × × Q ¯ H , M 1 = M ¯ 1 × M ¯ 1 × × M ¯ 1 γ , 1 γ H , W ( 0 ) = W { 0 } , W ( m ) = Π l P * Π l Q + k = 1 m 1 [ Π A m 1 A m k l P * Π A m 1 A m k l Q ] , W 1 ( m ) = M 1 + W ( m ) (53)

where m = 0 , 1 , θ .

Assuming that n—smallest of those natural numbers m, for each of which the inclusion C m z 0 W 1 ( m ) , proved from the point z 0 = f ¯ can complete the persecution for N steps [12].

Thus, in the specified 4.1, 4.2, in cases, the task is presented to calculate the geometric differences of Minkowski and study their geometric properties. More precisely, in the first case (30), the set W 1 ( τ ) = M 1 + W ( τ ) in the second case (53), the set W 1 ( m ) = M 1 + W ( m ) plays an important role in solving tasks.

5. Conclusion

This article discusses some essential properties of Minkowski sum and difference of sets and gives their proofs. It includes new theorems about Minkowski sum and difference of open and closed sets. The considered examples are presented for sets in the plane. It is difficult to measure in three dimensional spaces and is often mistaken. Even it is not explored in four dimensional polyhedrons. It may be easy and fast to calculate Minkowski sum and difference of sets in three dimensional spaces. Recorded results can be used to get sufficiency conditions to finish the game in differential games. We showed that if we take Minkowski sums of members of a family of pair wise disjoint convex sets, each of which has a constant description complexity, the radii of which are chosen by a suitable model, then the expected complexity of Minkowski sums is almost linear. It would be useful to prove or disprove that density and permutation models are equivalent in the sense that the value is asymptotically the same in both models for any family of pair wise disjoint convex sets. However, it is possible that there is a large class of density functions for which the density model gives a better upper bound.

Cite this paper: Mamatov, M. and Nuritdinov, J. (2020) Some Properties of the Sum and Geometric Differences of Minkowski. Journal of Applied Mathematics and Physics, 8, 2241-2255. doi: 10.4236/jamp.2020.810168.
References

[1]   Isaacs, R. (1965) Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. John Wiley and Sons, New York.

[2]   Pontryagin, L.S. (1981) Linear Differential Games of Pursuit. Math. USSR-Sb., 40/3, 285-303.
https://doi.org/10.1070/SM1981v040n03ABEH001815

[3]   Satimov, N. (1973) On the Pursuit Problem in Linear Differential Games. Differential Equations, 9, 2000-2009.

[4]   Minkowski, H. (1904) Verhandlungen des III international en Mathematiker-Kongresses in Heidelberg. 164-173.

[5]   Schneider, R. (1993) Convex Bodies: The Brunn-Minkowski Theory (Encyclopedia of Mathematics and Its Applications). Cambridge University Press, Cambridge, 44.
https://doi.org/10.1017/CBO9780511526282

[6]   Karpukhin, S.A. (2014) Complexity of Geometric Optimization by Rasterization of Minkowski Sums. Vychislitel’nye Metody i Programmirovanie, 15, 569-578.

[7]   Mamatov, M.Sh. (2009) About Application of a Method of Final Differences to the Decision a Prosecution Problem in Systems with the Distributed Parameters. Automation and Remote Control, 70, 1376-1384.
https://doi.org/10.1134/S0005117909080104

[8]   Mamatov, M.Sh. (2009) On the Theory of Differential Pursuit Games in Distributed Parameter Systems. Automatic Control and Computer Sciences, 43, 1-8.
https://doi.org/10.3103/S0146411609010015

[9]   Mamatov, M., Zunnunov, A. and Esonov, E. (2020) Quantitative Analysis of the Problem of Lion and Man in the Presence of a Circular Obstacle. Journal of Automation and Information, 52, 42-52.
https://doi.org/10.1615/JAutomatInfScien.v52.i2.40

[10]   Mamatov, M. and Sobirov, K. (2020) On the Theory of Position Pursuit Differential Games. Journal of Mathematical Sciences, 245, 332-340.
https://doi.org/10.1007/s10958-020-04694-4

[11]   Kilbas, A.A., Srivastava, H.M. and Trujillo, J.J. (2006) Theory and Applications of Fractional Differential Equations. Elsevier, Amsterdam, 500.

[12]   Mamatov, M.Sh., Durdiev, D.K. and Alimov, H.N. (2016) On the Theory of Fractional Order Differential Games of Pursuit. Journal of Applied Mathematics and Physics, 4, 1355-1362.

[13]   Mamatov, M.Sh., Toshmanov, E.B. and Alimov, H.N. (2015) Zwquasi-Linear Discrete Games of Pursuit Described by High-Order Equation Systems. Automatic Control and Computer Sciences, 49, 148-152.
https://doi.org/10.3103/S0146411615030050

[14]   Ramkumar, G.D. (1996) An Algorithm to Compute the Minkowski Sum Outer-Face of Two Simple Polygons. Proceedings of 12th Symposium on Computational Geometry, Philadelphia, PA, USA, May 1996, 234-241.
https://doi.org/10.1145/237218.237374

[15]   Kaul, A., O’Connor, M.A. and Srinivasan, V. (1991) Computing Minkowski Sums of Regular Polygons. Proceedings of 3rd Canadian Conference on Computational Geometry, Vancouver, Canada, 6-10 August 1991, 74-77.

[16]   Pontryagin, L.S. (1967) On Linear Differential Games II. Doklady Akademii Nauk SSSR, 175, 764-766.

 
 
Top