Let $K$ be a compact convex subset of $R^n$ which has some positive gaussian measure, say at least 1/2. For each nonzero vector $u \in R^n$, we define another compact convex set $K * u$ in the following way: Let $Z$ be the cylinder consisting of all lines $l$ parallel to $u$ such that the length of the segment $K \cap l$ is greater than or equal to $2||u||$. It may happen that $Z = \phi$. Naturally, Z is closed and convex. So formally, $$K * u = K \cap Z + \{tu \mid -1 \leq t \leq 1\} = ((K+u) \cup (K-u)) \cap Z$$ Now suppose $u_1,...,u_m$ are small(i.e. $||u_i|| \leq 1/10$, etc.) vectors in $R^n$. Define the sequence of bodies $K_1,...,K_m$ inductively by $K_0 = K, K_i = K_{i-1} * u_i$
There is a well-known result that states that the Gaussian measure of $K*u$ will be greater than or equal to the Gaussian measure of $K$. So all the $K_i$s are sufficiently large in that sense.
My question: Is there an efficient way for testing membership in these bodies $K_i$? More formally, does there exist an algorithm such that given a point, I can check only a polynomial number of constraints and say if the point belongs to $K_i$ or not?
For simplicity let us assume that $K$ is a polytope in n-dimension and its vertices will be provided to the algorithm as input. I think we can also just provide the equations of each of its sides as input to define the polytope.
Maybe there is no clear answer, but please post links to some references that have tried to solve such problems. I am also wondering if the "*" operation of the convex bodies has any other significance or meaning that is non-geometric. Maybe, a purely algebraic formulation can make the problem easier.
I noticed that even if we can find an efficient algorithm to check membership in $K$ and try to do that on $K_i$, this might not be efficient. $K_1$ is more like checking membership of $K$ two times, $K_3$ four times, and so on. So for $K_m$, we will have to make close to $2^m$ checks which are not efficient. $m$ is fixed but a parameter to the algorithm, so $2^m$ is not a constant.
I thought about using the paper "A LINEAR ALGORITHM FOR DETERMINING THE SEPARATION OF CONVEX POLYHEDRA" by David P. Dobkin & David G. Kirkpatrick (https://www.cs.ubc.ca/sites/default/files/tr/1983/TR-83-05_0_0.pdf), but still could not really connect to this problem.
