Some Properties of the Sum and Geometric Differences of Minkowski ()
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
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
, 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
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
,
(1)
Definition 2. The multiplication of set X and number
is defined to be the set
(2)
Definition 3. The Minkowski sum of any vector
and nonempty set
is defined to be the set
(3)
By the definition of the Minkowski difference of sets, the set
means the intersection of movement of the set X to vector
, which is
(4)
To prove this equality, it’s enough to show all
are belonged to set
and on the contrary. By the definition of the muliplication of set and number, expression
means that always there exists y element in the set Y such that
. Hence
.
Let
be vector of set
. Then by the definition of Minkowski difference of sets (4),
. By the definition of the Minkowski sum of sets, for all
elements there exists
element such that
,
. Since
,
. This equality is true for all
and such
, so we can write following expressions
(5)
Therefore, if
, then
.
Now, let
be vector of intersection
, then
for all
vectors. Hence there exists
vector such that
. Then
and
, since
. This equality is true for all
and such
, so we can write
, hence
. 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
.
Definition 5. The complement of given set X on the linear space E is written
and defined to be the set
(6)
Definition 6. The Minkowski operators of the multiple-valued function
, written as
and
, are defined to be operators
(7)
in here
be any set.
In especial condition multiple-valued function G is constant
for each
, then Minkowski operators become as Minkowski sum and difference:
(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
be nonempty sets on the linear space E and
. For any vectors
there exists a vector
such that
. (9)
Proof. Let
, then by the definition of Minkowski difference
. By the definition of Minkowski sum of sets for each
there exists vector
such
. Hence
. Therefore,
relation is true.
Lemma 2. For any nonempty sets X and Y on the linear space E following relation is true:
(10)
Proof. To prove this lemma we show that every element of
will be an element of
and on the contrary.
Let
be any vector. By the definition of the Minkowski difference of sets we can write
. For all
vectors
. We add
vector to both sides of this relation. Hence
. Since
relation, follows that
. Following example shows that each
vector does not belong to
set every time. Let
be given sets. Then
,
,
. Therefore,
.
Lemma 3. For any nonempty sets X and Y on the linear space E following relation is true:
(11)
Proof. Let
be any vector, then
. By the definition of the Minkowski difference of sets
. There exists
vector such that
and there exists
vector such that
. Hence
, therefore
.
Lemma 4. For any nonempty sets X and Y on the linear space E following relation is true:
(12)
Proof. Let
be any vector. By the definition of multiplication of sets and number there exists
vector such that
. Since
, we have
and
. Hence,
and
. It means that
. We can show that every vector
belongs to set
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:
(13)
in here
means boundary of the set X.
Proof. Let
be a vector, there exists
vector such that
.
means that for all neighborhoods
of
,
. We multiply both sides of these relations by number
and according to the lemma 4, we have
,
. It means that
. We can show that every vector
belongs to set
by using this method (13). Lemma has been proved.
Lemma 6. For any nonempty sets
and D on the linear space E following relation is true:
(14)
Proof. Let
be a vector. By the definition of Minkowski sum there exists
and
such that
. It means
. Hence, it follows
and
. Therefore,
. Following example shows that each
vector does not belong to
set every time (14). Let
be given sets. Then
,
. Therefore
.
Lemma 7. Let
be nonempty sets on the linear space E. If
, then
.
Proof. From
there exists set Z such that
. It means that each element
is an element of set X or an element of set Y or an element of both sets. This implies that for
there exists vector
or vector
such that
or
. By the definition of liner space we multiply both sides of these equalities by number
and it follows that
or
. Hence,
or
. It means equality
is true. Therefore,
.
Lemma 8. Let
be nonempty sets on the linear space E. If
, then
.
Proof. Let
be any vector of set
. By the definition of Minkowski sum of sets there exists
and
such that
. Since
, we have
and
. It means that
. Therefore
. Lemma has been proved.
Lemma 9. Let
be nonempty sets on the linear space E. If
, then
.
Proof. Let
be any vector. By the definition of the Minkowski difference
. Since
, it follows
,
.
According to the condition of the theorem,
and by the lemma 8,
. Hence,
. Therefore,
.
Lemma 10. For any nonempty sets X, Y and Z on the linear space E following relation is true:
(15)
Proof. Let
be any vector of set
, then there exists
and
such that
. Since
, we have
. We add vector
to both sides of these relations and we obtain
. It means that
. Hence,
.
Following example shows that each
vector does not belong to
set every time. Let
be given sets. Then we obtain
and
. Therefore,
.
Lemma 11. For any nonempty sets X, Y and Z on the linear space E following relation is true:
(16)
Proof. Let
be any vector of the set
, then by definition of the Minkowski sum, there exists vectors
and
such that
,
. Since
,
. According to
, we have
. Thus,
. By the lemma 2, we have
. Hence,
. Thus,
. Therefore,
.
Following example shows that each vector
does not belong to set
every time (15). Let
be given sets. Then
and
. Therefore,
.
Lemma 12. For any nonempty set X on the liner space E following equality is true.
(17)
Proof. Let
be any vector of the set
. By the definition of multiplication of sets and numbers, there exists
. Thus,
It means that for all
,
,
. This implies
. Consequently,
. We can show that every vector
belongs to set
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:
(18)
Proof. Let
be any vector. By the definition of the Minkowski difference of sets,
. It means that
for all vectors
. Thus,
and
. Then for all vectors
following relations is true
(19)
From this and by the lemma 12, it follows that
By the lemma 3, we can write following relations
(20)
Since
, we have
,
.
We can show that every vector
belongs to set
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:
(21)
Proof. Let
be any vector of set
. By the definition of the intersection of sets, it follows that
and
. By the definition of Minkowsli difference of sets, we have
and
. From these,
,
.
Now, let
be any vector. Then by the definition of the Minkowski difference of sets,
. By the definition of intersection of sets, we have
and
. Thus,
and
. It means that
. Therefore
. Theorem has been proved.
Theorem 3. For any sets
and any vector
, following equality is true
(22)
Proof. Let
be any vector. By the definition of the union of sets,
or
, or both relation will be true. By the definition of the Minkowski sum of sets, there exists
or
such that
or
. Thus,
or
. These imply
or
. It means that
. Therefore,
.
We can show that every vector
belongs to set
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:
(23)
Proof. Let
be any vector of set
. By the definition of the intersection of sets
and
. By the definition of the Minkowski difference of sets,
and
. Thus,
. According to the theorem 3,
(24)
Hence,
.
We can show that every vector
belongs to set
by using this method. Theorem has been proved. Therefore equality
is true (23).
Following theorems may be proved by using of the lemmas given above.
Theorem 5. If X be open (closed) set, then
will be open (closed) set too.
Proof. Suppose X be open set. Then for each
vectors there exists neighborhood
such that
. It is multiplied both sides of this relation by the number
, consequently
. In here
. It means that all points of set
are interior points, therefore
is open set.
Now suppose X be closed set. By the definition of closed set for all
vectors there exists neighborhoods
such that
. It is multiplied both sides of this relation by the number
, consequently
. It means that all points of set the
are adherent points, therefore
is closed set.
Theorem 6. Let
be nonempty sets on the linear space E. If either of them is an open set, then
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
vectors there exists it’s neighborhood
such that
. By the properties of Minkowski sum of the sets and according to the lemma 8 we can write following relation:
(25)
in here
is any vector of the set Y.
The neighborhood
is open ball with center
and radius r. By the definition of the Minkowski sum,
(26)
In here the set
is open ball with center
and radius r. Since (25) and (26), it follows
. Therefore,
is open set. First part of theorem has been proved.
Now we must prove second part of theorem. Suppose both sets
are closed. By the definition of closed sets, for all neighborhoods
and
of
and
we can record
,
. Hence,
. According to the lemma 6, it follows
. By the Minkowski sum
, then relation becomes
. It means that
is closed set. Theorem has been completely proved.
Theorem 7. Let
be nonempty sets on the linear space E. If the set X is open and the set Y is closed, then the set
will be the open one, and in other conditions it will be a closed set.
Proof. Suppose set
be closed. Then set
will be an open set. By the lemma 3,
. It means that, set
must be open. But according to the condition of theorem, set X is open and the set Y is closed so
will be closed and according to the theorem 1, set
will be closed too. By the theorem 2, set
will be closed. It means contradiction. Therefore, our suppose is not true and
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
is described by a differential equation of fractional order of the form
(27)
where
;
—fractional differentiation operator,
,
, A—n × n, B—p × n and G—q × n constant matrices,
—control parameters u—chasing player control parameter,
,
—runaway control parameter,
, P and Q—compacts,
—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
from function
, defined by the expression
(28)
Also in space
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
. We say that the differential game (27) can be completed from the initial position
during
, if there is such a measurable function
, what’s the solution to the equation
(29)
belongs to many M in the moment
for any measurable functions
,
,
.
Let us pass to the statement of the main results. Throughout what follows: 1) a terminal set M has the form
, where
—linear subspace
,
—subset of subspace L—orthogonal additions
; 2)
—orthogonal projection operator from
on L; 3) under operation
Minkowski geometric difference operation.
Let
-matrix
-exhibitor [11] and
,
,
,
;
(30)
In [12], it was proved that if in the game (27) for some
, turning on
(31)
then from the starting position
can complete the pursuit in time
.
4.2. Fractional Differential Games with Distributed Parameters
A controllable distributed system is described, described by equations of fractional order [11]
(32)
(33)
(34)
where z-unknown function from class
,
,
- rectangle with border L.
, T—arbitrary positive constant;
—thermal conductivity coefficients;
,
;
- partial fractional derivatives of Riemann-Liouville;
- partial fractional Riemann-Liouville integrals with respect to the corresponding variable [11].
—control parameters u—chasing player control parameter,
,
—runaway player control parameter,
, P and Q-compacts. Also in space
terminal set is allocated
where
,
. 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:
.
Let be
—some function with scope
. Then there is a finite-difference definition of the derivative of the order
at the point
:
(35)
where
;
,
. According to [11], if
, then the Grunwald derivative coincides with the Riemann-Liouville derivative. To approximate fractional Riemann-Liouville derivatives with respect to variables
at
on the segment
we use the Grunwald-Letnikov formula with an offset:
(36)
where
. 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
we get
(37)
(38)
here
.
Using a sufficient sign of the existence of a fractional derivative of the Riemann-Liouville
, on the segment
we get
(39)
here
(40)
Introducing the Derivative
on the segment
in the form of a finite difference
(41)
difference approximation of a fractional derivative
on the segment
can be written as
(42)
To find a solution to problem (32)-(34) in the region
introduce the grid
(43)
in increments
on x,
on y and
on t. Denote
(44)
Using equalities (35)-(40) for Equation (32), we write the explicit difference scheme
(45)
It is known that the difference scheme (45) is stable when
where
,
.
Decomposing functions
in the Taylor series and substituting the obtained relations in the difference scheme (45), we obtain
(46)
where
—some constants. Therefore, the difference scheme (45) approximates Equation (32) with the order
in time and second order in coordinates
.
In the case of a square grid, i.e. when
,
, for difference scheme (45) we have
(47)
(48)
where
.
The difference scheme (48) is stable when
(49)
where
,
.
Now for the convenience of presentation, we write problem (47), (48) in matrix form
,
,
, (50)
where
,
,
—H-dimensional matrices, H—the total number of nodes belonging to one layer, i.e. given
, where in
(51)
respectively,
(52)
initial vector,
,
—H-dimensional square matrix.
Let in
terminal set is allocated M. We say that in the game (47), (48) from the point
can complete the persecution for
steps, if by any sequence
runaway control can build such a sequence
management prosecution that decision
equations
,
, for some
gets on
.
Suppose that in game (50) the terminal set has the form
, where
—
-dimensional linear subspace
,
—subset of subspace L—orthogonal additions
in
. Next, through
denote the orthogonal projection matrix from
on L, and through
and
algebraic sum and geometric difference of Minkowski sets
respectively. Let be
(53)
where
.
Assuming that n—smallest of those natural numbers m, for each of which the inclusion
, proved from the point
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
in the second case (53), the set
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.