Hopefully I am using the right notion of convex combination. The following requires at most n+1 steps, however I do not know how complicated a step is.

Take the given point x and a vertex v visible from x. Thus the line through v and x passes through the polygon from v to x to a point p on a face or facet on the other side. x should be a convex combination of v and p. But p is a point interior to a polygon of smaller dimension, and (if I haven't missed my guess) is a convex combination of n or fewer vertices of the polytope. Now induct with p taking the role of x.

I can imagine having to search the vertex space to find v at each stage. However, coming up with a simplicial decomposition of certain parts of the polytope may speed up this part.

Gerhard "Ask Me About System Design" Paseman, 2012.02.14

Pto use it for manyx? – Zsbán Ambrus Feb 15 '12 at 10:31