0
$\begingroup$

I just want to make sure that the following algorithm is correct for computing the Minkowski difference of two shapes $A,B$:

$\text{Minkowski}(A,B) = \text{ CH } \{x: x = a - b \text{ for } a \in A, b \in B\}$ Where CH(S) is the convex hull of the set S and $a,b$ are the vertices of the two polygons.

Is it correct?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, assuming your polygons are convex.

Let $A=\text{conv}(\{a_1,\dotsc,a_n\})$ and $B=\text{conv}(\{b_1,\dotsc,b_m\})$. Then \begin{align*} A-B &= A+(-B) \\ &= \text{conv}(\{a_1,\dotsc,a_n\}) + \text{conv}(\{-b_1,\dotsc,-b_m\}) \\ &= \text{conv}(\{a_1,\dotsc,a_n\} + \{-b_1,\dotsc,-b_m\}) \end{align*} which is just what you said. The key step is pulling the conv out, which can be justified as follows.

(From here on, $A$ and $B$ are just arbitrary sets, not the polygons above.)

Lemma. If $A$ and $B$ are convex then $A+B$ is convex.

Proof. Direct.

Lemma. $\text{conv}(A+B) = \text{conv}(A)+\text{conv}(B)$.

Proof. ($\subseteq$) $A\subseteq\text{conv}(A)$ and $B\subseteq\text{conv}(B)$, so $A+B\subseteq\text{conv}(A)+\text{conv}(B)$. By the previous lemma, $\text{conv}(A)+\text{conv}(B)$ is convex, so $\text{conv}(A+B)\subseteq\text{conv}(A)+\text{conv}(B)$. ($\supseteq$) Let $x\in\text{conv}(A)+\text{conv}(B)$, say, $$ x = \sum_{i=1}^n \lambda_i a_i + \sum_{j=1}^m \mu_j b_j $$ where $\lambda_i > 0$, $\mu_j > 0$, $\sum_{i=1}^n \lambda_1 = 1$, $\sum_{j=1}^m \mu_j = 1$, $a_i\in A$, and $b_j\in B$. Then $$ x = \sum_{i=1}^n \lambda_i \Big(\sum_{j=1}^m \mu_j\Big) a_i + \sum_{j=1}^m \mu_j \Big(\sum_{i=1}^n \lambda_i\Big) b_j = \sum_{i=1}^n \sum_{j=1}^m \lambda_i \mu_j (a_i+b_j) $$ Since $a_i+b_j\in A+B$ and $\sum_{i=1}^n \sum_{j=1}^m \lambda_i \mu_j = \big(\sum_{i=1}^n \lambda_i\big) \big(\sum_{j=1}^m \mu_j\big) = 1\cdot1 = 1$, this shows that $x\in\text{conv}(A+B)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .