Sam Chiu-wai Wong

Tight Bounds for Approximate Carathéodory and Beyond

We present a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope’s vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem, which states that any point inside a polytope c…