Sampling from the Voronoi cell of a point
Too short for a comment... The following is intuitive bla bla, and feel free not buy it.

That seems extremely unlikely - assuming the points are uniformly distributed, the number of neighbours of the cell of $q$ is going to be $2^d$. Here is maybe a more formal argument. Pick a set of points on the unit hypersphere such that angle between any two points is at least, I dont know, 80 degrees. We know, that one can pick an exponential number of such points on the sphere without too much effort if the dimension is sufficiently large. Now, intuitively, for any subset of half the points, the Voronoi cell of the center of the sphere should have almost double the volume when compared to the cell volume with all the points. This inituitively implies you have to inspect all the points to get a good volume estimate. Which seems to imply, again intuitively, that sampling uniformly is going to be impossible, since the problems seems to be polynomially equivalent...