Abdeckungsproblem (Sender und Empfänger)

Ich versuche das folgende Abdeckungsproblem zu lösen.

Es gibt $n$ Sender mit einer Reichweite von 1 km und $n$ Empfänger. Entscheiden Sie in $O(n\log n)$ dass alle Empfänger von einem Sender abgedeckt werden. Alle Empfänger und Sender werden durch ihre $x$ und $y$ Koordinaten dargestellt.

Die fortschrittlichste Lösung, mit der ich kommen kann, ist $O(n^2\log n)$ . Sortieren Sie für jeden Empfänger alle Sender nach der Entfernung zu diesem aktuellen Empfänger. Nehmen Sie dann den Sender mit der kürzesten Entfernung und diese kürzeste Entfernung sollte innerhalb von 0,5 km liegen.

Aber der naive Ansatz sieht in der Zeitkomplexität viel besser aus . Berechnen Sie einfach den gesamten Abstand zwischen allen Paaren von Sender und Empfänger. $O(n^2)$

Ich bin nicht sicher, ob ich bei diesem Problem Algorithmen für die Bereichssuche anwenden kann. Zum Beispiel erlauben uns kd-Bäume, solche Bereiche zu finden, aber ich habe nie ein Beispiel gesehen und bin mir nicht sicher, ob es eine Art von Bereichssuche für Kreise gibt.

Die gegebene Komplexität setzt voraus, dass die Lösung der Sortierung ähnlich sein sollte. $O(n\log n)$

algorithms computational-geometry search-problem com
quelle

Wenn die erwartete Zeit

in Ordnung ist, könnten Sie einen

-Baum über den Sendern erstellen (Zeit

) und dann für jeden Empfänger eine Abfrage nach dem nächsten Nachbarn durchführen (Durchschnittswert) von

Zeit für jeden Empfänger). Dies sollte der Trick sein, aber ich gehe davon aus, dass Sie die Komplexität im schlimmsten Fall benötigen. Es scheint einige Tricks für die Beschleunigung zu geben, wenn Sie mehrere Abfragen nach dem nächsten Nachbarn in einem

-Baum ausführen.

O (n \log n)

$O(n \log n)$

k d

$kd$

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

k d

$kd$

utdiscant

Ich denke, ein Sweep-Line-Algorithmus kann den Trick machen: Sortieren Sie Sender und Empfänger nach x-Koordinaten und gehen Sie die Liste schrittweise durch. Eine geschickte Verwaltung des Satzes funktionsfähiger Sender ist unerlässlich.

Raphael

@Raphael, kannst du bitte etwas näher darauf eingehen? Es sieht so aus, als ob es im schlimmsten Fall sehr langsam wird.

com

Ich denke, es lohnt sich, einen Blick auf Fortunes Algorithmus zur Berechnung eines Voronoi-Diagramms in der Ebene zu werfen . Es funktioniert in

und mit einem Voronoi-Diagramm wird Ihr Problem einfach.

O (n \log n)

$O(n\log n)$

Syzygy

Antworten:

Sie können das Voronoi-Diagramm zusammen mit der Datenstruktur von Kirkpatrick verwenden, um dieses Problem zu lösen.

Wie Raphael und Syzygy vorgeschlagen haben, können Sie den Fortune-Algorithmus (Sweepline) verwenden , um das Voronoi-Diagramm zu erstellen. Zeit im schlimmsten Fall: . $\mathcal{O}(n \log n)$

Das Voronoi-Diagramm enthält eine Reihe von Polygonen, die jeweils einen Sender enthalten. Jeder Punkt innerhalb des Polygons ist dem Sender am nächsten. Wenn Sie also herausfinden können, welches Polygon den Empfänger enthält, können Sie den nächstgelegenen Sender finden, indem Sie irgendwie herausfinden, in welchem Polygon es sich befindet. Danach prüfen Sie, ob sich dieser Sender innerhalb von . $1\ \text{km}$

Um festzustellen, welches Voronoi-Polygon den Empfänger enthält, triangulieren Sie zunächst jedes Polygon im Diagramm. Jetzt haben Sie ein Dreiecksnetz. Als Nächstes verwenden Sie die Datenstruktur von Kirkpatrick, um ein beliebiges Dreieck zu lokalisieren, das einen bestimmten Punkt in der Zeit , im schlimmsten Fall. Der Aufbau der Kirkpatrick-Datenstruktur erfordert den ungünstigsten Fall . Sobald Sie das Dreieck kennen, kennen Sie das Polygon, das es enthält, und damit den nächsten Sender. Wenn Sie dies für alle Empfänger tun, ist dies im schlimmsten Fall . $\mathcal{O}(\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$

Jede Zelle in einem Voronoi-Diagramm ist ein konvexes Polygon, möglicherweise unbegrenzt.

...

Die Anzahl der Eckpunkte [eines Voronoi-Diagramms von n Stellen] V ≤ 2n-5

- www.cs.arizona.edu

$\Theta(v)$ $v$ $n$ $n$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ , aber die gesamte Triangulation nimmt auch . (Grundsätzlich werden wir nicht viele Zellen mit -Seitenantreffen, dies würde zu viele Dreiecke für einen planaren Graphen ergeben.) $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$

Realz Slaw
quelle