Arregle un conjunto de puntos . Ahora llega un punto de consulta , y el objetivo es producir un punto muestreado uniformemente al azar desde la celda Voronoi de en el conjunto .P ⊂ R d q rP ∪ { q }
A los efectos de esta pregunta, se puede suponer que 's de celdas de Voronoi siempre está limitada (por ejemplo siempre se encuentra en el casco convexo de ).q P
¿Se sabe algo sobre este problema?
Algunas restricciones:
- Podría querer más de una muestra de la célula Voronoi de . Estos deberían ser IID.
- Se me permite preprocesar los puntos, pero no puedo pasar tiempo exponencial en .
- La muestra debe generarse en tiempo sublineal en polinomio en idealmente.d
Tenga en cuenta que lo anterior descarta computar la celda Voronoi explícitamente. También tenga en cuenta que si bien un enfoque de muestreo de rechazo produciría una muestra uniforme, no está claro cómo hacerlo de manera eficiente.
cg.comp-geom
randomized-algorithms
voronoi
Suresh Venkat
fuente
fuente
Respuestas:
Demasiado corto para un comentario ... Lo siguiente es bla bla intuitivo, y siéntase libre de no comprarlo.
Eso parece extremadamente improbable: suponiendo que los puntos estén distribuidos uniformemente, el número de vecinos de la celda de será 2 dq 2d . Aquí hay quizás un argumento más formal. Elija un conjunto de puntos en la hiperesfera de la unidad de manera que el ángulo entre dos puntos sea al menos, no sé, 80 grados. Sabemos que se puede elegir un número exponencial de tales puntos en la esfera sin demasiado esfuerzo si la dimensión es lo suficientemente grande. Ahora, intuitivamente, para cualquier subconjunto de la mitad de los puntos, la celda Voronoi del centro de la esfera debería tener casi el doble del volumen en comparación con el volumen de la celda con todos los puntos. Esto implica de manera inituitiva que debe inspeccionar todos los puntos para obtener una buena estimación de volumen. Lo que parece implicar, nuevamente intuitivamente, que el muestreo uniforme será imposible, ya que los problemas parecen ser polinomialmente equivalentes ...
fuente