Convex Hull (2)

A Point which is defined by P = S ai Mi is inside the convex hull of {Mi}

Sai = 1

ai >= 0

lemme : the convex Hull of of a subset of a set is inside the convex hull of the set

recurrence demonstration

n = 1 => P = M

n = 2 => M1 M2        for 0<=t<=1   P = (1-t) M1 + t M2 = M1 + t M1M2

H : true for n, what about n+1

Pn+1 = S ai Mi = (1-an+1)S ai/(1-an+1) Mi + an+1Mn+1

= (1-an+1)M' + an+1 Mn+1