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

Question

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

Answer 1

(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.

Answer 2

I'll add here a full answer using @Apass.Jack helpful hints:

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.

Answer 3

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.