Addition of Arbitrary Shapes
You can't add apples and oranges but you can add their shapes.

To avoid ambiguity shapes whose sums I plan to consider will be finite-dimensional sets, say, subsets
of a space or a plane or a general vector space V. Talking of apples and oranges, these
probably more naturally perceived as sets of points not vectors. Then consider R3 as a set of points and select a
point (the origin) so that it would be possible to identify a point with the vector emanating from the origin and ending
at the point.
Returning to the sets of vectors, let X and Y be subsets of V. Then X+Y is a subset of V that consists of all the sums
A+B with A from X and B from Y. In other words, every element of X+Y can be represented as a sum of
elements of X and Y. This is very similar to the componentwise addition and is known as the "Parallelogram Rule".
For any two points A and B from X and Y, respectively, A+B is the point that completes the parallelogram with the three vertices O,A,and B.
Verification that the addition is associative and commutative is straightforward. Zero is {O}, the set that consists
of a single point - the origin.
This addition has some very desirable properties, especially when restricted to the collection of convex sets. Even more so when it's restricted to a pair of convex polygons.
- If any of the sets X, Y is translated (as a whole) so will be their sum X+Y
- If the origin is chosen differently, then the sum X+Y will be translated in the opposite direction but by the same distance as the origin.
- If X and Y are convex, so is X+Y
- Let X=B(A,R) and Y=B(B,S) be balls of radii R and S, respectively. Then X+Y=B(A+B,R+S) the
ball of radius R+S.
This addition has no inverse element.

However, there is a related operation that very nearly comes to being an inverse. The following
also shows that even when equivalent some definitions may (and often are) more fruitful than others.
Let's use a new symbol to denote the above
addition of shapes:
| (1) |
A B = {a+b: a A and b B}.
|
Note that if we use a-b in the definition instead of a+b we would gain precious little. Indeed, in case
where B is centrally symmetric the result will be exactly the same. Now let's reformulate the definition. First, let's
agree to write A+b for the set {a+b: a A}. Now,
| (2) |
A B = (A+b),
|
where union is taken over all b B. The definitions are equivalent
(check this) but (2) has a degree of freedom that provides for possible modifications. A curious
mind may ask, what if we use a set operation other than the union. Hermann Minkowski (1864-1909) after whom
(2) is known as Minkowski addition also defined (Minkowski) subtraction
| (3) |
A B = (A+b),
|
Both operations are widely used in image processing or, more specifically, morphological analysis of images, where they are known as dilation ( ) and erosion ( ).
The terminology is due to the fact that A B A A B
for any B. Dilation and erosion are not inverse of each other. There are two more useful operations that are defined in terms
of dilation and erosion: (for B with central symmetry)
| (4) |
Closing: O(A,B) = (A B) B
Opening: C(A,B) = (A B) B
|
Assuming B is a circle one may think of the opening as having a ball B roll inside A smoothing its corners (internal angles). More accurately
Theorem
O(A,B) = {B+x: B+x A}.
If Dc stands for the complement of D, then C(A,B) = O(Ac,B)c.
So closing may be thought of as having a ball B roll on the ouside of A smoothing its external angles. Both operation are used for
noise reduction and feature extraction.
Reference
- E.R.Dougherty and C.R.Giardina, Mathematical Methods for Artificial Intelligence and Autonomous Systems, Prentice Hall, 1988
- I.M.Yaglom and B.G.Boltyansky, Convex shapes, Nauka, Moscow, 1951. (in Russian)

Copyright © 1996-2008 Alexander Bogomolny
|