2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't think zhat your two statements can be used to proof the statement of he OP. So could you provide a proof? $\endgroup$ – miracle173 Nov 5 '18 at 1:53
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Nov 5 '18 at 2:08
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.