(I'm not sure how to title this as I have several related questions, so I did it with the most interesting one)
Let $P$ be a convex polytope. By Carathéodory's theorem, we can always decompose an $x \in P$ as a convex combination of at most $d+1$ other points in $P$: $x = \sum_{i = 0}^d \alpha_i u_i$, with $\sum_i \alpha_i = 1$ and $\alpha_i \geq 0$, where the $\{u_i\}_i$ are points in $P$.
Q1: Given an $x \in P$, what are good algorithms for finding its minimal decomposition, i.e., the one using at most $d+1$ extremal points?
Let $V = \{v_i\}_{i=0}^{n-1}$ be the set of all $n$ extremal points of a polytope $P = \text{conv}\,(V) \in \mathcal{R}^d$.
Q2: Can I also decompose $x$ with at most $d+1$ of the extremal points of $P$?
For the last question, suppose I have a $d$-dimensional polytope with $n \gg d$ extremal points. I now want to try to find a description of an $y$, which may not be in $P$, in terms of extremal points of $P$. This could be done with linear programming, given I had all of the $\{v_i\}_{i=0}^{n-1}$ (and it would tell me with certainty whether $y \in P$ or not).
Consider, though, that I cannot store all of the $n$ extremal points, but I can sample any reasonable $k$ of them. With those $k$, I want to answer whether $y \in P$ or not. I am also allowed to run the program with $r$ different random samples.
Q3: Are there any theorems of algorithms which would guide me on how big the number $k$ of sampled extremal points should be, and how many $r$ runs should I have, for reaching a certain bound on the probability that $y \in P$ or not?
This last one may be too specific a question, so I don't expect a fully developed answer or reference. If all you can think of is a hint on where to look for something similar to this, it'd already be very welcome.