Sampling from a particular region of a Voronoi diagram

We are given a finite set of points $\{p_1, ..., p_n\}$ in $\mathbb{R}^d$ which induce a Voronoi partitioning of the space into $n$ regions under, say, Euclidean metric. What is an efficient way of sampling from a particular region?

First try: sample a point ${x} \in \mathbb{R}^d$ and see it satisfies: $d(x, p_i) < d(x, p_j), \forall j \neq i$. Clearly this is not an efficient algorithm as, on average, I might discard $\frac{n-1}{n}$ portion of the points.

If you have the Voronoi diagram computed, here are two things you can do you improve efficiency:

• Restrict sampling to a box around the particular Voronoi cell (blue box in the image below)
• Restrict comparisons to Voronoi neighbors (red points below). That subset of points is sufficient to define the Voronoi cell.

If you are in a context where you can't construct the Voronoi diagram (high dimension d or unfortunately point placement causing Voronoi cells with low aspect ratio or large numbers of neighbors), it isn't clear there will be a good solution. See discussion of the problem in that context here.