Julia Community 🟣

WalterMadelim
WalterMadelim

Posted on

1

Convex hull of a Cartesian product

I find that this proposition is hardly found in textbooks. And its proof is not easily found on the internet (including asking ChatGPT). Therefore I write it down here as a reference.

function co(X::Set) return convex_hull(X) end
[Proposition1]   co(X) Γ— co(Y) == co(X Γ— Y) # "Γ—" is the times---Cartesian Product symbol
[Corollary]  ⨉_i co(S_i) = co(⨉_i S_i), # "⨉" is the bigtimes---Cartesian Product symbol

Proof:
Assume there is a point denoted by (x, y) ∈ co(X) Γ— co(Y), where
x ∈ co(X) with x = _p * _x + p_ * x_ for some
_x, x_ ∈ X and _p, p_ β‰₯ 0 and _p + p_ == 1;
y ∈ co(Y) with y = _q * _y + q_ * y_ for some
_y, y_ ∈ Y and _q, q_ β‰₯ 0 and _q + q_ == 1;
We need to prove that (x, y) ∈ co(X Γ— Y).
Indeed, there are 4 points in X Γ— Y as follows
# point => its coefficient in a convex combination
(_x, _y) => _p * _q 
(_x, y_) => _p * q_
(x_, _y) => p_ * _q
(x_, y_) => p_ * q_
such that their convex combination is precisely (x, y).
Therefore we've proved (x, y) ∈ co(X Γ— Y).
The reverse direction is easier, hence omitted.
Therefore [Proposition1] holds.
Furthermore, co(X) Γ— co(Y) Γ— co(Z)
= co(X Γ— Y) Γ— co(Z)
= co(X Γ— Y Γ— Z).
Likewise, we conclude that [Corollary] holds.
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

Collapse
 
waltermadelim profile image
WalterMadelim β€’

This proposition was used in [Proposition 2, ref 1].

ref 1: doi.org/10.1016/S0167-6377(98)00050-9

Collapse
 
brunompacheco profile image
Bruno M. Pacheco β€’

Not every point in the convex hull of X (Y) can be written as a convex combination of just two points in X (Y), as by the CarathΓ©odory's theorem. This makes the actual proof a bit more intricate, as X and Y may have different dimensions. Nevertheless, I believe the general idea is right. It should be enough that (x,y) is a convex combination of k points in co(X x Y) iff x and y are convex combinations of the k points projected into their respective spaces. Making k large enough does the trick.