Minkowski difference of two convex polygonsI just want to make sure that the following algorithm is correct for computing the Minkowski difference of two shapes A,B: Minkowski ( A , B ) = CH { x : x = a − b for a ∈ A , b ∈ B }Where CH(S) is the convex hull of the set S and a,b are the vertices of the two polygons.

Question

Minkowski difference of two convex polygonsI just want to make sure that the following algorithm is correct for computing the Minkowski difference of two shapes A,B:  Minkowski  (  A  ,  B  )  =   CH   {  x  :  x  =  a  −  b   for   a  ∈  A  ,  b  ∈  B  }Where CH(S) is the convex hull of the set S and a,b are the vertices of the two polygons.

efterynzl · Accepted Answer

Step 1Yes, assuming your polygons are convex.Let   A  =  conv  (  {      a    1    ,  …  ,      a    n    }  ) and   B  =  conv  (  {      b    1    ,  …  ,      b    m    }  ). Then                     A        −        B                            =        A        +        (        −        B        )                                          =        conv        (        {                  a          1                ,        …        ,                  a          n                }        )        +        conv        (        {        −                  b          1                ,        …        ,        −                  b          m                }        )                                          =        conv        (        {                  a          1                ,        …        ,                  a          n                }        +        {        −                  b          1                ,        …        ,        −                  b          m                }        )            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.Step 2Lemma.   conv  (  A  +  B  )  =  conv  (  A  )  +  conv  (  B  )Proof. (  ⊆)   A  ⊆  conv  (  A  ) and   B  ⊆  conv  (  B  ), so   A  +  B  ⊆  conv  (  A  )  +  conv  (  B  ). By the previous lemma,   conv  (  A  )  +  conv  (  B  ) is convex, so   conv  (  A  +  B  )  ⊆  conv  (  A  )  +  conv  (  B  ). (  ⊇) Let   x  ∈  conv  (  A  )  +  conv  (  B  ), say,  x  =      ∑          i      =      1        n        λ    i        a    i    +      ∑          j      =      1        m        μ    j        b    j  where       λ    i    &amp;gt;  0,       μ    j    &amp;gt;  0,       ∑          i      =      1        n        λ    1    =  1,       ∑          j      =      1        m        μ    j    =  1,       a    i    ∈  A, and       b    j    ∈  B. Then   x  =      ∑          i      =      1        n        λ    i              (            ∑          j      =      1        m        μ    j              )            a    i    +      ∑          j      =      1        m        μ    j              (            ∑          i      =      1        n        λ    i              )            b    j    =      ∑          i      =      1        n        ∑          j      =      1        m        λ    i        μ    j    (      a    i    +      b    j    )Since       a    i    +      b    j    ∈  A  +  B and       ∑          i      =      1        n        ∑          j      =      1        m        λ    i        μ    j    =            (            ∑          i      =      1        n        λ    i              )                  (            ∑          j      =      1        m        μ    j              )        =  1  ⋅  1  =  1, this shows that   x  ∈  conv  (  A  +  B  ).

Minkowski(A,B)= CH {x:x=a-b 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. It is correct?

Answered question

Answer & Explanation

New Questions in High school geometry