Probenahme aus der Voronoi-Zelle eines Punktes

Fixiere eine Menge von Punkten . Nun kommt ein Abfragepunkt an, und das Ziel besteht darin, einen Punkt erzeugen, der gleichmäßig zufällig aus der Voronoi-Zelle von in der Menge abgetastet wird . $n$ $P \subset \mathbb{R}^d$ $q$ $r$ $q$ $P \cup \{q\}$

Für die Zwecke dieser Frage können Sie annehmen, dass die Voronoi-Zelle von immer begrenzt ist (zum Beispiel liegt immer in der konvexen Hülle von ). $q$ $q$ $P$

Ist etwas über dieses Problem bekannt?

Einige Einschränkungen:

Ich möchte vielleicht mehr als eine Probe aus der Voronoi-Zelle von . Dies sollte IID sein. $q$
Ich darf die Punkte vorverarbeiten, aber ich kann keine exponentielle Zeit in verbringen . $d$
Die Probe sollte idealerweise zeitlich sublinear in und polynomial in . $n$ $d$

Beachten Sie, dass das oben Gesagte die explizite Berechnung der Voronoi-Zelle ausschließt. Beachten Sie auch, dass ein Ablehnungsstichprobenansatz zwar eine einheitliche Stichprobe ergeben würde, es jedoch nicht klar ist, wie dies effizient durchgeführt werden kann.

cg.comp-geom randomized-algorithms voronoi Suresh Venkat
quelle

Gibt es einen Grund dafür, dass es nicht sofort funktioniert, die üblichen Volumenschätzungs-Random-Walk-Techniken zur Erzeugung gleichmäßig zufälliger Stichproben in konvexen Körpern in Polynomzeit zu verwenden?

David Eppstein

Ich hätte es klarstellen sollen. Es sollte möglich sein, sie zu verwenden, da das Mitgliedschaftsorakel berechnet werden kann, aber die Laufzeit zum Generieren eines Samples ist ziemlich teuer (zumindest ist es eine lineare Zeit, da Sie die Voronoi-Zelle anhand der Einschränkungen der n Halbebene beschreiben). Daher der sublineare Vorbehalt.

Suresh Venkat

Ah, ich habe den sublinearen Teil verpasst.

David Eppstein

Sie können jedes Polytop als Voronoi-Zelle realisieren. Sie müssen also mindestens in der Lage sein, ein Polytop vorzuverarbeiten, damit Sie schneller IID-einheitliche Proben daraus ziehen können, als jedes Mal den vollständigen Zufallsspaziergang durchzuführen. das scheint schwer genug selbst?

Sasho Nikolov

Antworten:

Zu kurz für einen Kommentar ... Das Folgende ist intuitiv bla bla, und Sie können es nicht kaufen.

Das äußerst unwahrscheinlich erscheint - die Punkte unter der Annahme gleichmäßig verteilt sind , die Anzahl der Nachbarn der Zelle von sein wird $q$ $2^d$ . Hier ist vielleicht ein formelleres Argument. Wählen Sie eine Reihe von Punkten auf der Hypersphäre der Einheit so, dass der Winkel zwischen zwei beliebigen Punkten mindestens 80 Grad beträgt, ich weiß nicht. Wir wissen, dass man ohne großen Aufwand eine exponentielle Anzahl solcher Punkte auf der Kugel auswählen kann, wenn die Dimension ausreichend groß ist. Intuitiv sollte die Voronoi-Zelle im Mittelpunkt der Kugel für jede Teilmenge der Hälfte der Punkte fast doppelt so groß sein wie das Zellvolumen mit allen Punkten. Dies bedeutet, dass Sie alle Punkte überprüfen müssen, um eine gute Volumenschätzung zu erhalten. Was wiederum intuitiv zu implizieren scheint, dass eine einheitliche Abtastung unmöglich sein wird, da die Probleme polynomiell äquivalent zu sein scheinen ...

Sariel Har-Peled
quelle

Das ist ein interessantes Argument. Würde ein solches Argument jedoch nicht bedeuten, dass Sie das Volumen eines durch Halbebenen definierten konvexen Körpers nicht abschätzen können, von dem wir wissen, dass wir es können?

Suresh Venkat

Nicht wirklich - wenn Sie alle Eingaben lesen können, schlägt dieses Argument fehl ....

Sariel Har-Peled

Nun, ich darf die Eingabe nach Belieben vorverarbeiten.

Suresh Venkat