I'm in trouble trying to generate samples following a particular distribution which is not numerically known perfectly. Let us consider a $R^n$ space provided with an orthonormal base $( e_{1},...,e_{n} )$ and N points $(X^{(1)},...,X^{(N)})$ in this $R^n$ space (the family of point is growing during the process). I want to draw uniform samples in the following subset of R^n : $$\begin{aligned}SubSet = R^n & - \bigcup_{i=1}^{N}\left (\{\zeta \in R^{n}, \zeta_{j} \leq X^{(i)}_{j}, \forall j \in (1,\dots,n) \} \right )\\& - \bigcup_{i=1}^{N}\left (\{\zeta \in R^{n}, \zeta_{j} \geq X^{(i)}_{j}, \forall j \in (1,\dots,n) \} \right ), \end{aligned} $$ where $\cdot_{j}$ refers to the $j^{th}$ component. When the space dimension is taken as dimension $2$, one can obtain the following figure : in red the SubSet, in green the $X^{(i)}$ points, in blue the areas to discard

As the $(X^{(i)})$ family is growing during the process, my SubSet becomes more and more small during the process. In dimension 2, the red areas are easy to compute and symbolic calculation is OK for a classic computer. Thus it is easy to draw uniform samples. But when the dimension arises, it becomes really complicated. I took some time looking at importance sampling in order to draw samples in the red areas without calculating them but the proposal distribution is really hard to define since it is both multimodal and multivariate distribution.

Do you think importance sampling is a good candidate that deserve some exploration ? How would you define the proposal distribution ? Do you have any other idea of how to do such thing ?

P.S. : From any point in the $R^n$ space, it is numerically not costly to know if it is in blue area or not since the number of points $X^{(i)}$ is rather low.