A question related to the Minkowski sum

1000 Views Asked by At

In the context of geometry, the Minikowski sum of convex sets $A$ & $B$ is defined as,

$A+B$={$a+b | a\in A,b\in B$}.

As an illustration of this concept, we can consider the Minkowski sum of an origin-symmetric square $K$ of side length $l$ and a disk $L = \epsilon B$ of radius $\epsilon$,that is centered at $0$ ($B$ is the unit ball). Now, the total area of the combined object, say $V(K+L)$, which consists of,

  1. A rounded square composed of a copy of $K$,
  2. Four rectangles of area $l \epsilon$,
  3. Four quarter disks of radius $\epsilon$.

Note: Assume these objects are in the Euclidean plane.

My question:

why is the combined object a rounded square? What is the intuition behind Minkowski sum(in the context of geometry)?.

1

There are 1 best solutions below

2
On BEST ANSWER

A) I answer first to your final question "what is the intuition behind Mikowski sum ?"

The shapes I will consider are convex polygons, with notations

$$ A = A_1A_2\cdots A_m \ \ \ \text{and} \ \ \ \ B= B_1B_2\cdots B_n$$

(we assume a cylic numbering convention $A_{m+1}=A_1$, etc.)

I am aware of 3 different ways to consider Minkowski sum $ A \oplus B$ :

1) (fig. 1 : left) by considering the sum of all vectors

$$\vec{OC_{p,q}}:=\vec{OA_p}+\vec{OB_q}$$ for a certain origin point $O$ and then taking the convex hull (featured in green) of all points $C_{p,q}$ represented by little stars (the convex hull of a set of points is the smallest convex set containing all these points).

Remark The choice of origin point $O$ is unimportant : changing it into $O'$ results in a simple translation by vector $\vec{OO'}$ meaning that we have the same result ($A \oplus B$ is defined up to a translation).

enter image description here

Fig. 1 : Two ways to build the Minkowski sum.

2) (Fig. 1 : right) By defining it as the (green) shape "halfway from $A$ and $B$" (up to a proper normalization) in an operation called "morphing between shapes" with notation $\tfrac12(A+B)$.

3) (Fig. 2) still another way, by working on borders : consider the two families of vectors $A_{p+1}-A_p=\vec{A_pA_{p+1}}$ and $\vec{B_qB_{q+1}}$, merge them into a big bunch of vectors, call them $\vec{v_1}, \vec{v_2}, \cdots \vec{v_{m+n}}$, then do the inverse operation by constructing the shape whose "borders" are

$$\vec{v_1}, \vec{v_1}+\vec{v_{2}}, \vec{v_1}+\vec{v_2}+\vec{v_{3}}, \cdots$$

You get in this way the borderline of Minkowski sum of $A$ and $B$.

Remark : the first operation is akin to a derivation, the second one, its inverse, to an integration.

enter image description here

Fig. 2 : Constructing $A \oplus B$ in a third way.

B) (Fig. 3) Now, for the issue about the Minkowski sum of a polygon and a disk $rB$ with radius $r$, where $B$ is the unit disk (a disk can be considered as the limit of regular polygons with $n$ sides when $n \to \infty$) and the formula of its area :

$$area( A \oplus rB)=area(A)+Lr+\pi r^2\tag{1}$$

($A \oplus rB$ is called the dilated set in the domain of "mathematical morphology/computational geometry). The vizualisation of the decomposition into elementary areas presented under the following form is a model of graphical proof... I wish this figure helps you in the full understanding about the rounded parts.

enter image description here

Fig. 3 : A visual proof for formula (1)

Remark : for more, here is an excellent source.