I am given a multivariate distribution, that maps each point of $\mathbb{R}^n$ to its probability of being drawn as sample and, the convolution $\mathcal{S_r}\times\mathcal{M}$ of a manifold $\mathcal{M}: \mathbb{R}^m\mapsto\mathbb{R}^n$, $m\lt n$, of $\mathbb{R}^n$ with the $n$-dimensional hypersphere $\mathcal{S_r}:\sum_{i=1}^n x_i^2\le\mathcal{r}^2$

Question:

- what are general and non-trivial methods for sampling an arbitrary multidimensional distribution inside the convolution of a hyper-sphere with a manifold?
(I am especially interested in methods, whose runtime depends on the number of samples generated in the convolution).

Clarification: I consider rejection methods (i.e. drawing a samples from $\mathbb{R}^n$ and only reporting those in the convolution) as trivial. Edit:

The **motivation for the question** is a possible suggestion of an answer to Finding energy minimizing path.

My idea is to start by generating a sufficiently dense sampling of the $xy$-plane by using e.g. Poisson Disk Sampling (a.k.a. Blue Noise), construct that pointset's Delaunay Triangulation with edge-weights complying to the energy-cost model and then calculate the least cost path.

Then, once the initial path is calculated, iterate by increasing the sampling density in an $\epsilon$-hose around the path, reconstruct the Delauny and recalculate the shortest path.

Whether that algorithm is efficient, depends however crucially on the ability to restrict Poisson Disk Sampling to a path's $\epsilon$-hose.
For the special case of an equal distribution I don't see a problem in restricting the sampling to ever finer grid-cells covering the path, but for other distributions I have no idea, how to proceed in an analogous way without introducing sampling bias.
That idea is elaborated in my answer to that question