Corrija um conjunto de pontos . Agora chega um ponto de consulta , e o objetivo é produzir um ponto amostrado uniformemente aleatoriamente a partir da célula Voronoi de no conjunto .P ⊂ R d q r q P ∪ { q }
Para os propósitos desta pergunta, você pode assumir que a célula Voronoi de está sempre limitada (por exemplo, sempre fica no casco convexo de ).q P
Existe algo conhecido sobre esse problema?
Algumas restrições:
- Talvez eu queira mais de uma amostra da célula Voronoi de . Estes devem ser IID.
- Estou autorizado a pré-processar os pontos, mas não posso gastar tempo exponencial em .
- A amostra deve ser gerada no tempo sublinear em polinômio em idealmente.d
Observe que o exposto acima exclui o cálculo explícito da célula Voronoi. Observe também que, embora uma abordagem de amostragem por rejeição produza uma amostra uniforme, não está claro como fazê-lo com eficiência.
cg.comp-geom
randomized-algorithms
voronoi
Suresh Venkat
fonte
fonte
Respostas:
Muito curto para um comentário ... A seguir, é intuitivo bla bla e fique à vontade para não comprá-lo.
Isso parece extremamente improvável - assumindo que os pontos sejam distribuídos uniformemente, o número de vizinhos da célula de será2 dq 2d . Aqui está talvez um argumento mais formal. Escolha um conjunto de pontos na unidade hiperesfera, de modo que o ângulo entre dois pontos seja pelo menos, não sei, 80 graus. Sabemos que é possível escolher um número exponencial de tais pontos na esfera sem muito esforço se a dimensão for suficientemente grande. Agora, intuitivamente, para qualquer subconjunto de metade dos pontos, a célula Voronoi do centro da esfera deve ter quase o dobro do volume quando comparada ao volume da célula com todos os pontos. Isso implica inituitivamente que você deve inspecionar todos os pontos para obter uma boa estimativa de volume. O que parece implicar, mais uma vez intuitivamente, que a amostragem uniforme será impossível, uma vez que os problemas parecem ser polinomialmente equivalentes ...
fonte