Fix a set of $n$ points $P \subset \mathbb{R}^d$. Now a query point $q$ arrives, and the goal is produce a point $r$ sampled uniformly at random from the Voronoi cell of $q$ in the set $P \cup \{q\}$.
For the purpose of this question, you can assume that $q$'s Voronoi cell is always bounded (for example $q$ always lies in the convex hull of $P$).
Is there anything known about this problem ?
Some constraints:
- I might want more than one sample from $q$'s Voronoi cell. These should be IID.
- I am allowed to preprocess the points, but I cannot spend time exponential in $d$.
- The sample should be generated in time sublinear in $n$ and polynomial in $d$ ideally.
Note that the above rule out computing the Voronoi cell explicitly. Also note that while a rejection sampling approach would yield a uniform sample, it's not clear how to do it efficiently.