<p>Too short for a comment... The following is intuitive bla bla, and feel free not buy it.</p>

<p>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...</p>

CC BY-SA 3.0
2013-01-09T05:35:46.353Z
That's an interesting argument. However, wouldn't such an argument suggest that you can't estimate the volume of a convex body defined by halfplanes, which we know we can do ?
Suresh Venkat
CC BY-SA 3.0
2013-01-09T23:17:53.910Z
Not really - if you can read all the input then this argument fails....
Sariel Har-Peled
CC BY-SA 3.0
2013-01-09T23:20:31.170Z
Well I am allowed to preprocess the input any way I see fit.
Suresh Venkat
CC BY-SA 3.0
2013-01-09T05:11:13.147Z
2013-01-09T05:11:13.147Z
Sariel Har-Peled
<blockquote>
  <p>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 <strong>uniformly
  at random</strong> from the Voronoi cell of $q$ in the set $P \cup \{q\}$.</p>
</blockquote>

<p>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$). </p>

<p>Is there anything known about this problem ? </p>

<p>Some constraints:</p>

<ul>
<li>I might want more than one sample from $q$'s Voronoi cell. These should be IID. </li>
<li>I am allowed to preprocess the points, but I cannot spend time exponential in $d$. </li>
<li>The sample should be generated in time sublinear in $n$ and polynomial in $d$ ideally. </li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2013-01-07T01:23:58.820Z
Is there some reason that it doesn't just immediately work to use the usual volume-estimation random-walk techniques for generating uniformly random samples within convex bodies in polynomial time?
David Eppstein
CC BY-SA 3.0
2013-01-07T03:34:37.427Z
I should have clarified. It should be possible to use them since the membership oracle can be computed, but the running time to generate a sample is quite expensive (at the very least it's linear time because you describe the voronoi cell in terms of the n halfplane constraints). Hence the sublinear proviso.
Suresh Venkat
CC BY-SA 3.0
2013-01-07T04:32:54.010Z
Ah, I missed the sublinear part.
David Eppstein
CC BY-SA 3.0
2013-01-09T08:51:01.183Z
you can realize any polytope as a Voronoi cell. so at a minimum you'd need to be able to preprocess a polytope so that you can draw IID uniform samples from it faster than doing the full random walk each time. this seems hard enough itself?
Sasho Nikolov
<cg.comp-geom><randomized-algorithms><voronoi>
Sampling from the Voronoi cell of a point
Suresh Venkat
# Sampling from the Voronoi cell of a point

(Asked by: username_0 on 2013-01-07)

> 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.

**Tags:** cg.comp-geom, randomized-algorithms, voronoi
> **Comments:**
> **username_1**: Is there some reason that it doesn't just immediately work to use the usual volume-estimation random-walk techniques for generating uniformly random samples within convex bodies in polynomial time?  
> **username_0**: I should have clarified. It should be possible to use them since the membership oracle can be computed, but the running time to generate a sample is quite expensive (at the very least it's linear time because you describe the voronoi cell in terms of the n halfplane constraints). Hence the sublinear proviso.  
> **username_1**: Ah, I missed the sublinear part.  
> **username_2**: you can realize any polytope as a Voronoi cell. so at a minimum you'd need to be able to preprocess a polytope so that you can draw IID uniform samples from it faster than doing the full random walk each time. this seems hard enough itself?  

---

## 1 answers

### Answer by username_3 on 2013-01-09. Score: 1

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...

> **Comments:**
> **username_0**: That's an interesting argument. However, wouldn't such an argument suggest that you can't estimate the volume of a convex body defined by halfplanes, which we know we can do ?  
> **username_3**: Not really - if you can read all the input then this argument fails....  
> **username_0**: Well I am allowed to preprocess the input any way I see fit.  

---

