Convex hull of a Cartesian product

WalterMadelim — Fri, 16 May 2025 02:43:45 +0000

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.

Julia Community 🟣: WalterMadelim

Convex hull of a Cartesian product