Convex Hull - Minkowski Addition and Convex Hulls

Minkowski Addition and Convex Hulls

See also: Minkowski addition and Shapley–Folkman lemma

The operation of taking convex hulls behaves well with respect to the Minkowski addition of sets.

  • In a real vector-space, the Minkowski sum of two (non-empty) sets S1 and S2 is defined to be the set S1 + S2 formed by the addition of vectors element-wise from the summand-sets
S1 + S2 = { x1 + x2 : x1 ∈ S1 and x2 ∈ S2 }.

More generally, the Minkowski sum of a finite family of (non-empty) sets Sn is the set formed by element-wise addition of vectors

∑ Sn = { ∑ xn : xn ∈ Sn }.
  • For all subsets S1 and S2 of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls
Conv( S1 + S2 ) = Conv( S1 ) + Conv( S2 ).

This result holds more generally for each finite collection of non-empty sets

Conv( ∑ Sn ) = ∑ Conv( Sn ).

In other words, the operations of Minkowski summation and of forming convex hulls are commuting operations.

These results show that Minkowski addition differs from the union operation of set theory; indeed, the union of two convex sets need not be convex: The inclusion Conv(S) ∪ Conv(T) ⊆ Conv(S ∪ T) is generally strict. The convex-hull operation is needed for the set of convex sets to form a lattice, in which the "join" operation is the convex hull of the union of two convex sets

Conv(S)∨Conv(T) = Conv( S ∪ T ) = Conv( Conv(S) ∪ Conv(T) ).

Read more about this topic:  Convex Hull

Famous quotes containing the words addition and/or hulls:

    “As easy mayst thou fall
    A drop of water in the breaking gulf,
    And take unmingled thence that drop again,
    Without addition or diminishing,
    As take from me thyself and not me too.”
    —William Shakespeare (1564–1616)

    “To anybody who can hold the Present at its worth without being inappreciative of the Past, it may be forgiven, if to such an one the solitary old hulk at Portsmouth, Nelson’s Victory, seems to float there, not alone as the decaying monument of a fame incorruptible, but also as a poetic approach, softened by its picturesqueness, to the Monitors and yet mightier hulls of the European ironclads.”
    —Herman Melville (1819–1891)