# How to prove that the erosion of a convex set by a convex set will result in a convex set?

How to prove that given convex sets A and B, the erosion of A by B will result in C - a convex set, too?

I was given this question as a test-preparation, and I think it shuold be a proof, but I don't know how to prove it.

A convex set is a set where every line connecting 2 dots in the set, must be part of the set, too. Now, if I would take a convex set A, I don't see how can I use erosion on it to get a non-convex set. Every example I try to create ends up the empty set, because the "holes" in B that are suppose to the "holes" in C, make C be all-zero.

Can someone help with a direction to a proof? Thanks

(Convexity is closed under intersection) Given a family of convex set $$C_i$$, where $$i\in I$$ for some index set $$I$$, then $$\cap_{i\in I}C_i$$ is convex.

In other words, the intersection of convex sets are convex.

Proof. Suppose two points $$p$$ and $$q$$ are in $$\cap_{i\in I}C_i$$. That is, for each $$i\in I$$, $$p\in C_i$$ and $$q\in C_i$$. Consider $$L$$, the line segment between $$p$$ and $$q$$. By the definition of convexity, $$L\subseteq C_i$$. That is $$L\subseteq \cap_{i\in I}C_i$$. By the definition of convexity again, $\cap_{i\in I}C_i$\$ is convex.

(Convexity is closed under translation) If $$C$$ is a convex set, then $$C_t=\{x+t\mid x\in C\}$$ is also convex.

In other words, if you translate a convex set, you will get a convex set.

Proof is skipped.

(Convexity is closed under erosion) Suppose $$A$$ is a convex set. Let $$B$$ be another set. Then the erosion of $$A$$ by $$B$$ is convex.

Proof. I will let you figure out given the above two lemmas. Another hint is given in the statement itself, which is, you do not need $$B$$ to be convex at all.

Is the erosion of $$A$$ by $$B$$ always empty?

Imagine both $$A$$ and $$B$$ are disks centered at the origin. $$A$$ is a huge while $$B$$ is a very small. Then the "erosion" by $$B$$ can only remove a small stripe along the circumference of $$A$$. The inner part of $$A$$ will not be "eroded". So the erosion of $$A$$ by $$B$$ will keep a significant part of $$A$$.

You can also check an example on Wikipedia.

• I don't think zhat your two statements can be used to proof the statement of he OP. So could you provide a proof? – miracle173 Nov 5 '18 at 1:53
• In general, I will wait for the OP to respond. Since you asked, however, I will provide a further hint. Try finding a formula for the erosion of A by B so that the first lemma might be applicable. – Apass.Jack Nov 5 '18 at 2:08

Erosion of $$A$$ by $$B$$ can be represented as $$\cap_{b\in B} A_{-b}$$, meaning a intersection of all sets A translated by $$-b$$ for all $$b$$ in $$B$$.

Given the 2nd lemma - Convexity is closed under translation, so all the sets in the intersection are convex. Using that, and the 1st lemma - Convexity is closed under intersection, we end up with a convex set :-)

Using this proof it is obvious that B need not be convex set at all, since no matter what is the shape of B, the translation of A by any $$-b \in B$$ would still be convex set if A is convex.

This can be deduced from the definition of the erosion. According to the wiki article we define $$B_z=\{b+z\mid b\in B\}$$ and the erosion of the 'binary image' $$A$$ by the 'structuring element' $$B$$ as $$A\circleddash B=\{z \in E\mid B_z\subseteq A\}$$ The symbol $$E$$ is either $$\mathbb{R}^n$$ or $$\mathbb{Z}^n.$$

Now assume that $$A$$ is convex and $$z_1, z_2 \in A \circleddash B$$ and $$z_3$$ is on the line between $$z_1$$ and $$z_2.$$ We have to show that $$z_3 \in A \circleddash B$$, which means $$B_{z_3}\subseteq A.$$

Then there is a $$\lambda_3 \in [0,1]$$ such that

$$z_3=\lambda_3 z_1+(1-\lambda_3) z_2.$$

If $$t_3 \in B_{z_3}$$ then $$t_3-z_3 \in B$$ and so $$t_3-z_3+z_1 \in B_{z_1}\subseteq A$$ $$t_3-z_3+z_2 \in B_{z_2}\subseteq A$$ Because both numbers are in the convex set $$A$$ and
$$\lambda_3(t_3-z_3+z_1)+(1-\lambda_3)(t_3-z_3+z_2)=t_3$$ we have $$t_3 \in A.$$ This holds for all $$t_3 \in B_{z_3}.$$ So $$B_{z_3} \subseteq A$$ and this implies $$z_3 \in A\circleddash B.$$ Therefore $$A\circleddash B$$ is convex.