# Brunn-Minkowski Inequality

** Definition 1 **

Let \( \mathcal U \) and \( \mathcal V \) be two sets of points in the plane. We will define their half-sum \( \mathcal U\oplus \mathcal V \)
as:

\( \mathcal U\oplus \mathcal V=\{X: X \) is the midpoint of the segment \( AB \) where \( A \) and \( B \) are arbitrary points of \( \mathcal U \) and \( \mathcal V \) respectively.\( \} \)

** Problem 1 **

Assume that \( \mathcal U=\{U\} \) is a single point and \( \mathcal V \) is an arbitrary set. Then \( \mathcal U\oplus \mathcal V \) is the image of \( \mathcal V \) under under the homothety with center \( U \) and coefficient \( \frac12 \).

This is obvious and follows straight from the definition of homothety.

To any set of points \( \mathcal U \) in the plane we can be associate the following set of vectors \( \overrightarrow{\mathcal U}=\{\overrightarrow{OX}: X\in \mathcal U\} \), where \( O \) is a fixed point in the plane (in the sequel we will call it the *origin*).
From now on let us assume that \( O \) is some fixed point in the plane.
For any two sets \( \mathcal U \) and \( \mathcal V \) in the plane
we define the sum of the sets \( \overrightarrow{\mathcal U} \) and \( \overrightarrow{\mathcal V} \) as:
\[ \overrightarrow{\mathcal U}+\overrightarrow{\mathcal V}=\{ \overrightarrow u+\overrightarrow v: \overrightarrow u\in \overrightarrow{\mathcal U}, \overrightarrow v\in
\overrightarrow{\mathcal V}\}.\]

** Problem 2 **

Let \( \mathcal U=\{U\} \) be a single point, and \( \mathcal V \) an arbitrary set in the plane.
If we consider all vectors to originate from \( O \), then the set \( \overrightarrow{\mathcal U}+\overrightarrow{\mathcal V} \) is a translation of \( \overrightarrow{\mathcal V} \) for the vector \( \overrightarrow{OU} \).

This follows immediately from the definition of "\( + \)".

** Theorem 1 **

The set of all endpoints of the vectors from \( \overrightarrow{\mathcal U}+
\overrightarrow {\mathcal V} \) (if those vectors are set to originate from \( O \))
is similar to the set \( \mathcal U\oplus \mathcal V \) with the coefficient of similarity \( \frac12 \).

Consider two points \( U\in\mathcal U \) and \( V\in\mathcal V \). Then
\( \overrightarrow{OU}\in\overrightarrow{\mathcal U} \) and
\( \overrightarrow{OV}\in\overrightarrow{\mathcal V} \). Let \( W^{\prime} \) be the midpoint of the segment \( UV \). The point \( W \) for which
\( \overrightarrow{OW}=\overrightarrow{OU}+\overrightarrow{OV} \) lies on the line \( OW^{\prime} \) and \( \overrightarrow{OW^{\prime}}=\frac12\overrightarrow{OW} \). The statement of the theorem now trivially follows.

By its definition \( \overrightarrow{\mathcal U}+
\overrightarrow {\mathcal V} \) is a set of vectors. If we consider these vectors as vectors originating from \( O \), we can look at the set of their endpoints. Let us denote this set by \( \mathcal U+ \mathcal V \). We saw that this set is similar to \( \mathcal U\oplus \mathcal V \) and twice as large. Therefore many of the theorems about \( \mathcal U+ \mathcal V \) will be identical (or very analogous) to the theorems about
\( \mathcal U\oplus \mathcal V \).
Let us also notice that if one of the sets \( \mathcal U \) and \( \mathcal V \) is translated, then their sum and the half-sum will also be translated by the appropriate vector.

*Remark.*
The sum \( \mathcal U+\mathcal V \) is often called the *Minkowski sum* of the sets \( \mathcal U \) and \( \mathcal V \).

** Problem 3 **

Assume that \( \mathcal U \) and \( \mathcal V \) are convex sets.
Prove that \( \mathcal U\oplus \mathcal V \) and \( \mathcal U+ \mathcal V \) are convex as well.

It is enough to prove that \( \mathcal U+ \mathcal V \) is convex. In order to do that consider two different points \( A, B\in\mathcal U+ \mathcal V \). There are two points \( A_U\in\mathcal U \), and \( A_V\in\mathcal V \) such that \( \overrightarrow{OA}=\overrightarrow{OA_U}+\overrightarrow{OA_V} \). Similarly there are points \( B_U \) and \( B_V \) such that \( \overrightarrow{OB}=\overrightarrow{OB_U}+\overrightarrow{OB_V} \). To prove that the entire segment \( AB \) belongs to \( \mathcal U+\mathcal V \) we will take an arbitrary point from that segment and prove that it belongs to \( \mathcal U+\mathcal V \). For each point \( X\in AB \) there exists a real number \( \lambda\in(0,1) \) such that \( \overrightarrow{OX}=\lambda \overrightarrow{OA}+(1-\lambda)\overrightarrow {OB} \) (see Theorem 1 from Important results in geometry). If we consider the vector \( \overrightarrow{OP}=\lambda\overrightarrow{OA_U}+(1-\lambda)\overrightarrow{OB_U} \) as a vector originating from \( O \), then its other endpoint \( P \) must belong to \( A_UB_U \) (converse of Theorem 1 from Important results in geometry). Notice that the entire segment \( A_UB_U \) belongs to \( \mathcal U \) which implies that \( \overrightarrow{OP}\in\overrightarrow{\mathcal U} \). Similarly if \( \lambda \overrightarrow{OA_V}+(1-\lambda)\overrightarrow{OB_V}=\overrightarrow{OQ} \) then \( Q\in A_VB_V \), so \( \overrightarrow{OQ}\in\overrightarrow{\mathcal V} \) therefore
\( \overrightarrow{OP} +\overrightarrow{OQ}\in \overrightarrow{\mathcal U} + \overrightarrow{\mathcal V} \). Since \( \overrightarrow{OP}+\overrightarrow{OQ}=\lambda \overrightarrow{OA}+(1-\lambda)\overrightarrow{OB}=\overrightarrow{OX} \) we get \( X\in \mathcal U+\mathcal V \).

The following problems are not difficult, but it is important for you to do them. Solving them will make you more familiar with the Minkowski sum and you will have an easier time reading the rest of the paper.

** Problem 4 **

Find \( \mathcal U\oplus \mathcal V \), if:

**(a)** \( \mathcal U \) and \( \mathcal V \) are parallel segments \( AB \) and \( CD \).
**(b)** \( \mathcal U \) and \( \mathcal V \) are non-parallel segments \( AB \) and \( CD \).
**(c)** \( \mathcal U \) and \( \mathcal V \) are two rectangles \( ABCD \) and \( PQRS \) such that \( AB\|PQ \).

**(a)** \( \mathcal U\oplus \mathcal V \) is the midsegment of \( ABCD \), i.e. the segment connecting the midpoints of the sides \( AC \) and \( BD \) (or \( AD \) and \( BC \) depending on which of the two is larger set).
**(b)** We can assume that \( ABCD \) form a convex quadrilateral (since we can translate one of the segments without changing the outcome of their half-sum). Denote by \( M \) the midpoint of \( AC \), and by \( N \) the midpoint of \( BD \). Let \( P \) and \( Q \) be the midpoints of \( AD \) and \( BC \). It is easy to prove that \( AB\oplus CD \) is the parallelogram \( PMQN \).
**(c)** In this case it is easier to find \( ABCD+PQRS \). It will be the rectangle with sides
\( AB+PQ \) and \( BC+QR \).

** Problem 5 **

Find examples of pentagons and triangles whose sums are pentagon, \( 6 \)-gon, \( 7 \)-gon, and \( 8 \)-gon.

Consider the square \( AFDE \) and denote by \( B \) and \( C \) the midpoints of \( AF \) and \( FD \). In all of our examples below, the considered pentagon will be \( ABCDE \). Denote by \( X \) the center of the square \( AFDE \).

**(a)** The sum \( ABCDE+\triangle BCX \) will be the pentagon \( ABC^{\prime}D^{\prime}E^{\prime} \) where \( E^{\prime} \) belongs to the extension of the ray \( AE \) over \( E \) and satisfies \( EE^{\prime}=BX \), \( D^{\prime} \) belongs to the extension of the ray \( AD \) over \( D \) such that \( DD^{\prime}=BC \), and \( C^{\prime} \) belongs to the extension of the ray \( BC \) (over \( C \)) and satisfies \( CC^{\prime}=BC \).
**(b)** In this case consider the triangle \( BC_1X \) where \( C_1 \) is the point on the ray \( XC \) over \( X \) such that \( CC^{\prime}=XC \). Then \( ABCDE+BC_1X=ABC_1C_1^{\prime}D^{\prime\prime}E^{\prime} \) where \( E^{\prime} \) is defined as above; \( D^{\prime\prime} \) is a point such that \( E^{\prime}D^{\prime\prime}\|ED \) and \( DD^{\prime\prime}\|BC_1 \); \( C_1^{\prime} \)
is a point such that \( CC_1^{\prime}D^{\prime\prime}D \) is a parallelogram.
**(c)** Denote by \( M \) the midpoint of \( AE \). Then \( ABCDE+BC_1M \) is a \( 7 \)-gon.
**(d)** \( ABCDE+BC_1E \) is an \( 8 \)-gon.

** Theorem 2 (Brunn-Minkowski) **

If \( \mathcal U \) and \( \mathcal V \) are convex sets in the plane, then \[ \sqrt{S_{\mathcal U+\mathcal V}}\geq \sqrt{S_{\mathcal U}}+\sqrt{S_{\mathcal V}}.\]

The following proof uses the integral calculus. If you are not familiar with the integrals, please skip this proof, you won’t need it for understanding the remaining text nor for solving the problems.

Since the area of each of the sets \( \mathcal U \), \( \mathcal V \), and \( \mathcal W=\mathcal U+\mathcal V \) is invariant under translations we may assume that the projections of \( \mathcal U \) and \( \mathcal V \) to the \( Ox \) axis are \( [0,a] \) and \( [0,b] \) respectively. Denote by \( A=S_{\mathcal U} \), \( B=S_{\mathcal V} \), and \( C=S_{\mathcal W} \).
For each \( p\in [0,a] \) consider the line parallel to \( Oy \) that passes through \( (p,0) \). Denote by \( \mathcal U(p) \) the intersection of that line with the set \( \mathcal U \). Similarly we define \( \mathcal V(p) \) and \( \mathcal W(p) \). Denote by
\( f(p) \), \( g(p) \), and \( h(p) \) the lengths of the segments \( \mathcal U(p) \),
\( \mathcal V(p) \),
and \( \mathcal W(p) \).
Then \( A=\int_0^a f(x)\,dx \), \( B=\int_0^b g(x)\,dx \), and
\( C=\int_0^{a+b} h(x)\,dx \). Define
\( F(x)=\int_0^x f(t)\,dt \) and \( G(x)=\int_0^x g(t)\,dt \). The functions
\( \alpha(t)=F^{-1}(At) \) and \( \beta(t)=G^{-1}(Bt) \) are increasing functions that map
\( [0,1] \) to \( [0,a] \) and \( [0,b] \) respectively. The function
\( \gamma(t)=\alpha(t)+\beta(t) \)
is increasing as well and maps \( [0,1] \) to \( [0,a+b] \).
Then \( C=\int_0^1h(\gamma(t))\gamma^{\prime}(t)\,dt \). Since \( \mathcal W(\gamma(t))
\supseteq \mathcal U(\alpha(t))+\mathcal V(\beta(t)) \) we obtain
\( h(\gamma(t))\geq f(\alpha(t))+ g(\beta(t)) \). Therefore
\[ C\geq \int_0^1 [f(\alpha(t))+g(\beta(t))]\cdot [\alpha^{\prime}(t)+\beta^{\prime}(t)]\,dt.
\]
Notice that \( f(\alpha(t))\alpha^{\prime}(t)=[F(\alpha(t))]^{\prime}=[At]^{\prime}=A \) and similarly \( f(\beta(t))\beta^{\prime}(t)=B \). Notice also that
\[ f(\alpha(t))\beta^{\prime}(t)+g(\beta(t))\alpha^{\prime}(t)\geq 2\sqrt{f(\alpha(t))\alpha^{\prime}(t)\cdot
g(\beta(t))\beta^{\prime}(t)]}=2\sqrt{AB}.\] Therefore
\[ [f(\alpha(t))+g(\beta(t))]\cdot [\alpha^{\prime}(t)+\beta^{\prime}(t)]\geq A+B+2\sqrt{AB}=(\sqrt A+\sqrt B)^2.\] Hence \[ C\geq \int_0^1\left(\sqrt A+\sqrt B\right)^2\,dt=\left(\sqrt A+\sqrt B\right)^2. \]
This is exactly what we had to prove.

** Problem 6 (Dušan Djukić, IMO 2006) **

Assign to each side \( b \) of a convex polygon \( \mathcal P \) the
maximum area of a triangle that has \( b \) as a side and is contained in
\( \mathcal P \). Show that the sum of the areas assigned to the sides of
\( \mathcal P \) is at least twice the area of \( \mathcal P \).

Assume that \( \mathcal P=A_1A_2\dots A_n \) and that
\( A_1 \) is the origin. Denote by \( \mathcal P^{\prime} \) be the centrally symmetric polygon to \( \mathcal P \) with respect to \( A_1 \). Let \( \mathcal Q=\mathcal P+\mathcal P^{\prime} \). The \( 2n \)-gon \( \mathcal Q=B_1B_2\dots B_{2n} \) is centrally symmetric. Assume that \( C \) is its center of symmetry. The side-lengths of \( \mathcal Q \) are exactly the side-lengths of \( \mathcal P \), each side appearing twice. Consider the side \( B_iB_{i+1} \) of the polygon \( \mathcal Q \). Then \( B_{i+n}B_{i+n+1}\|B_iB_{i+1} \), \( B_{i+n}B_{i+n+1}=B_iB_{i+1} \), and let \( A_jA_{j+1} \) be the side of \( \mathcal P \) corresponding to \( B_iB_{i+1} \). The distance between the lines \( B_{i+n}B_{i+n+1} \) and \( B_iB_{i+1} \) is exactly twice the length of the longest altitude of \( \mathcal P \) corresponding to \( A_jA_{j+1} \). Therefore the assigned area to the side \( A_jA_{j+1} \) is equal to \( \frac14S_{B_iB_{i+1}B_{n_i}B_{n+i+1}} \). However since \( S_{B_iB_{i+1}B_{n_i}B_{n+i+1}}=2(S_{B_iB_{i+1}C}+S_{B_{n+i}B_{n+i+1}C}) \) we know that the total sum of the areas assigned to the sides of \( \mathcal P \) is equal to \( \frac14\cdot 2S_{\mathcal Q}=\frac 12S_{\mathcal Q} \). Now our task is equivalent to proving that \( \frac12S_{\mathcal Q}\geq 2S_{\mathcal P} \). According to the Brunn-Minkowski inequality we have
\( \sqrt{S_{\mathcal Q}}\geq \sqrt{S_{\mathcal P}}+\sqrt{S_{\mathcal P^{\prime}}}=2\sqrt{S_{\mathcal P}} \) which completes the proof.