Volumen de células voronoi dentro de la bola.

Question

Tengo el siguiente problema:

Nos deja denotar una bola con centro de $C$ y radio de $R$ en $\mathbb{R}^d$ como $B(C, R)$. Dado que una unidad de la bola de $B(0, 1)$ y el vector $u$ tiene una distribución uniforme en el interior de la bola: $u \sim U(B(0, 1))$. A continuación, nos muestra $M$ puntos $v_1, \dots, v_M$ que son distribuidos de manera uniforme en el balón $B(0, 1)$ , y la distancia entre $u$ e $v_i$ no es mayor que $r$, que es $v_i$ son yo.yo.d. en $B(0, 1) \cap B(u, r)$. Cómo calcular el volumen de la celda de Voronoi de $u$ dentro de la bola de $B(0, 1)$? Necesito un límite superior aquí.

Puedo obtener sólo son estimaciones muy aproximadas, que no dependen de la dimensión del espacio de $d$ y radio de $r$. Es claro que los valores deseados se crece monótonamente como $r$ creciendo y si ponemos $r \ge 2$, a continuación, $v_1, \dots, v_M$ están distribuidos de manera uniforme en el interior de la bola de $B(0, 1)$. Así, $u, v_1, \dots, v_M$ son yo.yo.d. y distribuidos de manera uniforme en $B(0, 1)$. La definición rigurosa del valor que necesito para estimar (hasta un factor de escala del volumen de la unidad de la bola): $$ \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}) $$ Está claro que $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}$ = $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_i | q \sim U(B(0,1))\}$, por lo que las expectativas de todos los volúmenes son iguales y la suma de todos los volúmenes es igual a $1$. Por lo tanto $$ \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}) = \frac{1}{M+1}$$ Sólo queda multiplica por el volumen de la unidad de la bola.

Pero como $r$ hace menos de $2$ el volumen disminuye, por lo que sería como para obtener estimaciones de la que se tenga en cuenta. Por otra parte, he realizado experimentos numéricos que muestra que la estimación también debería depende de la dimensión del espacio de $d$. Aquí es normal y la escala del registro de parcelas ($M = 10$):

En el caso más general, cuando $r < 2$ todavía tenemos que $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_j | q \sim U(B(0,1))\}$ = $\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_k | q \sim U(B(0,1))\}$ y la suma de tales probabilidades de $u$ e $v_1, \dots, v_M$ es igual a $1$, por lo tanto tenemos: $$ \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~u | q \sim U(B(0,1))\}) + M \mathbb{E}_{u, v_1, \dots, v_M} (\mathbb{P}\{ q~\text{belongs to the Voronoi cell of}~v_1 | q \sim U(B(0,1))\}) = 1$$

Si hemos sido capaces de encontrar otra ecuación de estimación o en la relación de volúmenes, entonces el problema estaría resuelto.

Yo le agradezco su ayuda, ideas, documentos, libros y así sucesivamente. Gracias por su ayuda!

Answer 1

No es una solución completa, pero demasiado largo para un comentario:

Para $r \ll 1$, el volumen de la $B(u,r) \ll$ volumen de $B(0,1)$ (esp. si $d$ es alta), por lo que una aproximación podría estar disponible:

(1) $P(B(u,r) \subset B(0,1)) \approx 1$, lo que nos permite simplificar $B(0,1)\cap B(u,r) = B(u,r)$, conservando la simetría de la distribución de $v_i$.

(2) $P(q \in B(0,1) - B(u,r)) \approx 1$.

Ahora, $q \in Voronoi(u)$ fib $\forall i: dist(q,u) < dist(q,v_i)$. Suponiendo (1) y (2), podemos decir:

(3) $P(dist(q,u) < dist(q,v_i)) \approx 1/2$, dado que aproximadamente la mitad de $B(0,1)\cap B(u,r) = B(u,r)$ está más cerca de a $q$ que $u$ es. [Considerar la hyperplane a través de $u$ que es $\perp$ para el segmento de la línea de $L$ de $u$ a $q$. El hyperplane biseca $B(u,r)$ en dos medias bolas. Cualquier $v_i$ en la media pelota lejos de $q$ satisface $dist(q,v_i) > dist(q,u)$. De hecho, incluso en el medio de la bola en el mismo lado de la $q$ hay algunos $v_i$ satisfacción $dist(q,v_i) > dist(q,u)$, pero si $r \ll 1$ , a continuación, con alta prob $r \ll |L|$ es decir $q$ está "muy lejos" de $u$ por lo que la aproximación debe ser bueno.]

(4) $P(q \in Voronoi(u)) \approx 1/2^M$, ya que el $v_i$ son independientes.

Esta aproximación debe ser bastante bueno para $r \ll 1$ y esp. en alta $d$, debido a la relación de volúmenes va como $r^d$. E. g. parece que han simulado el caso de $r=0.1, d = 5$ y me pregunto si es preciso habrá. (No he podido comprobar el gráfico a mí mismo ya no hablar de lo $M$ usted utiliza.)

Por CIERTO, esta aproximación se ignora totalmente la parte de $Voronoi(u)$ que es en realidad dentro de $B(u,r)$. Efectivamente estamos diciendo cualquier parte de la celda de Voronoi será demasiado pequeño para la materia, y en su lugar se espera que el volumen es casi enteramente de los raros casos en que una gran parte de la $B(0,1)$ está disponible como $Voronoi(u)$ porque todos los $v_i$ pasan a ser recogido en el "otro lado". Sin embargo, este tipo de aproximación se puede romper cuando se $M$ es muy grande, como la $1/2^M$ plazo se convierte en pequeño y la parte de $Voronoi(u)$ dentro $B(u,r)$ podría convertirse en la dominante (pero todavía muy pequeño) plazo.

Para valores intermedios de $r, d, M$, parece que el problema muy difícil de resolver exactamente, pero la intuición probablemente todavía un poco sostiene. El factor clave es, probablemente, la relación de volumen de $r^d$, aunque ahora que $B(u,r) \cap B(0,1)$ no es una bola significativamente complica las cosas. Pero al menos esto puede dar una idea de por qué para mayor $d$ la probabilidad es cercana a la de bajo valor ($1/2^M$) pero inferior $d$ la probabilidad es cercana a la $1/(M+1)$ valor.

Por CIERTO, estás seriamente interesado en todo lo posible a$r,d,M$? Si tu aplicación tiene ciertos rangos que son de más interés podría haber mejores soluciones y aproximaciones disponibles. (E. g. el caso de $M=1$ podría ser exactamente solucionable...)