Let $P_1,P_2...P_r$ be a set of convex polytopes with $n_r$ vertices in 3 dimensions. These polytopes basically represent uncertainties of '$r$' number of 3d-points respectively in space. The global uncertainty polytope $P$ is a Minkowski sum of these individual Polytopes in a particular application that I'm working in.
$P = P_1+P_2+...+P_r$
The application demands computation in less than a millisecond for 15 polytopes of 5-7 vertices each, which makes analytical computation not practical. Also addition of points uniformly sampled from the interior of these convex polytopes $P_1,P_2,...P_r$ resulted in a distribution that is way smaller than the $P$ polytope making it conservative for the application. This means the probability of all the samples from each link reaching a maximum or minimum bound in a particular direction is very small. These polytopes as I said in the beginning are uncertainties and there is a need to have a polytope sum with higher probability of being reached and not being conservative.
So I want to approximate this polytope by taking a convex hull of the set generated by adding points sampled uniformly from each of the polytopes.
What is the guarantee that I will end up in a distribution of higher probability, if a minkowski sum approximation is performed by adding $N$ set of points sampled uniformly from the interior of the polytopes?
According to my understanding, the sampling events are independent but non identical as the polytopes are not similar. Is there a systematic way to approximate this sum?
I also think that by sampling only regions around vertices in each of the polytopes, the resulting sum distribution is not conservative and not optimistic. Let us say we only sample only in the margin of the polytope, then the probability of sampling set of points in a particular direction in space is a binomial distribution
$B(r,1/(n_d))$
$r$ is the number of polytopes. $n_d$ is the number of directions.
The probability is very very small to sample points maximal or minimal in particular direction which will let the sum of these points hit the margin of the analytically computed sum Polytope.
What is the systematic way to sample from the individual polytopes to get an approximate sum distribution? And what is the probabilistic guarantee that this distribution can provide and how to estimate it?
This plot 1 shows the conservative nature of the minkowski sum of 10 polytopes in 2d. Uniform Sampling of 10,000 set of 10 polytope samples is done and the resulting distribution is very small. This is the main reason I would like to approximate.
