Finden Sie den kürzesten paarweisen Abstand von Punkten in o (n log n)?

Die folgende Übung wurde an von mir betreute Schüler verteilt:

Entwickeln Sie bei $n$ Punkten in der Ebene einen Algorithmus, der ein Punktpaar findet, dessen Abstand zwischen allen Punktpaaren minimal ist. Der Algorithmus sollte in der Zeit laufen $o(n^2)$ .

Es gibt einen (relativ) einfachen Divide and Conquer-Algorithmus, der die Aufgabe in der Zeit löst $\Theta(n \log n)$ .

Frage 1 : Gibt es einen Algorithmus, der das gegebene Problem genau im ungünstigsten Fall löst $\mathcal{o}(n \log n)$ ?

Was mich vermuten ließ, dass dies möglich sein könnte, ist ein Ergebnis, das ich in einem Vortrag gesehen habe (Referenz geschätzt). Es wurde etwas in der Richtung angegeben, dass nicht mehr als eine konstante Anzahl $c \in \mathbb{N}$ von Punkten in der Ebene um einen Punkt $p$ innerhalb eines Kreises mit dem Radius $r \in \mathbb{R}$ , wobei $r$ der minimale Abstand zwischen zwei der beteiligten Punkte ist . Ich denke, $c=7$ , die Punkte bilden ein gleichseitiges Sechseck mit $p$ in der Mitte (im Extremfall).

In diesem Fall sollte der folgende Algorithmus das Problem in $n$ Schritten lösen .

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Beachten Sie, dass dies in linearer Zeit geschieht (angeblich), da nur eine konstante Anzahl von Punkten in rnicht weiter entfernt sein kann als mvon p(unter der Annahme der obigen Aussage); Nur diese Punkte müssen untersucht werden, um ein neues Minimum zu finden. Es gibt natürlich einen Haken; Wie implementieren Sie nextNeighbour(möglicherweise mit Vorverarbeitung in linearer Zeit)?

Frage 2 : eine Reihe von Punkten Lassen und einen Punkt . Sei mit $R$ $p \notin R$ $m \in \mathbb{R}$

$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$

und

$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$ .

Angenommen, ist endlich. Ist es möglich, mit minimalem Abstand von in (amortisierter) Zeit ? (Sie können davon ausgehen, dass konstruiert wird, indem Sie die untersuchten Punkte nacheinander hinzufügen .) $R_{p,m}$ $p' \in R_{p,m}$ $p$ $\mathcal{O}(1)$ $R$ $p$

ds.data-structures cg.comp-geom Raphael
quelle

Ich würde vorschlagen, mit "engstes Paar" als Schlüsselwort zu suchen.

Yoshio Okamoto

Dies ist mittlerweile alles Standardmaterial, siehe die ersten beiden Kapitel hier: goo.gl/pLiEO

Sariel Har-Peled

Ps. Wenn Sie die erwartete Zeit wünschen, können Sie sogar die Delaunay-Triangulation berechnen, die den Mindestabstand enthält.

Domotorp

Nach Frage 1 schreiben Sie: "Es kann nicht mehr als eine konstante Anzahl von Punkten in der Ebene um einen Punkt p innerhalb eines Kreises mit dem Radius r angeordnet werden, wobei r der minimale Abstand zwischen p und einem anderen Punkt ist." Dies ist sicherlich nicht wahr: Sie können beliebig viele Punkte auf dem Kreis mit dem Radius r nehmen. Ihre Aussage ist wahr, wenn r der minimale Abstand zwischen zwei beliebigen Punkten ist. In diesem Fall ist der Beweis recht einfach.

Domotorp

Die erste Frage ist Lehrbuchmaterial, wie bereits erwähnt: definitiv kein Forschungsniveau. Ich verstehe nicht , die zweite Frage: für jedes , das Sie entweder fragen ist nicht vorhanden oder ist der nächste Nachbar zu in . Wie unterscheidet sich das von Frage 1? Worüber tilgen Sie sich (dh wenn es sich um eine Datenstrukturfrage handelt, wie lauten die Aktualisierungen und Abfragen)?

m

$m$

p^{'}

$p'$

p

$p$

R

$R$

Sasho Nikolov

Antworten:

In Standardmodellen ist es unmöglich, das Problem in weniger als Zeit zu lösen , z. B. mithilfe algebraischer Entscheidungsbäume. Dies folgt aus der Arbeit von Yao und Ben-Or, die zeigt, dass es in diesem Modell nicht möglich ist, zu entscheiden, ob ein Satz von Eingangsnummern alle unterschiedlich ist oder nicht (siehe http://people.bath.ac.uk/masnnv /Teaching/AAlg11_8.pdf ). Stellen Sie sich bei Ihrem Problem vor, dass alle auf der realen Linie sind. Wenn zwei Punkte gleich sind, wäre Ihre Ausgabe zwei Punkte mit dem Abstand Null, andernfalls nicht. Eine Lösung für Ihr Problem würde also auch das Problem DISTINCT NUMBERS lösen. Wenn Sie annehmen möchten, dass alle Ihre Punkte unterschiedlich sind, fügen Sie einfach zum $cn\log n$ $n$ $i\epsilon$ $x_i$ Eingaben des Problems DISTINCT NUMBERS. In diesem Fall sind die Zahlen nicht alle unterschiedlich, wenn Ihre Ausgabe höchstens ist. (Obwohl in diesem Fall müssen Sie ein Versprechen Version verwenden , wenn die Differenz von je zwei verschiedenen Zahlen zumindest , aber ich denke , der gleiche Beweis zeigen Werke , die Sie auch benötigen in diesem Fall.) $n\epsilon$ $2n\epsilon$ $\Omega(n\log n)$

domotorp
quelle

In der Tat, danke. Das beantwortet auch Frage 2 (negativ).

Raphael

Das von Ihnen erwähnte Problem ist anscheinend auch als Element Distinctness Problem bekannt .

Raphael

Die Referenz von @Sariel Har-Peled ( goo.gl/pLiEO ) präsentiert einen praktischen linearen Zeitalgorithmus zum Finden des nächsten Paares. Dieses Dokument geht direkt auf dieses Argument ein und erklärt, dass es nicht gilt, da der Algorithmus ein leistungsfähigeres Berechnungsmodell verwendet.

Kevin Cline

Ja, aber die Frage wurde speziell für die Worst-Case-Laufzeit gestellt. Ich stimme jedoch zu, dass alle meine Beobachtungen bereits in Sariels These erscheinen.

Domotorp

Es gibt einen randomisierten linearen Algorithmus für die erwartete Zeit von Rabin; siehe zB Rabin wirft eine Münze auf Liptons Blog.

David Eppstein
quelle

Soweit ich Frage 2 verstehe, liefert Rabins Algorithmus auch eine Art Antwort darauf. Bei jedem Zeitschritt ist die Datenstruktur ein Raster mit einer Zellenbreite, die kleiner ist als der kleinste Abstand zwischen den bisher gesehenen Punktpaaren, geteilt durch (sodass keine Zelle mehr als einen einzelnen Punkt enthält). Um die Abfrage in Frage 2 zu beantworten, müssen Sie nur einer Zelle im Raster zuordnen und eine konstante Anzahl von Zellen um sie herum betrachten. Wenn nach der Analyse des Algorithmus der eingestellte Eingabepunkt in zufälliger Reihenfolge untersucht wird, beträgt die amortisierte Aktualisierungszeit für das Gitter pro neuem Erwartungspunkt. $\sqrt{2}$ $p$ $O(1)$

Sasho Nikolov
quelle

Übrigens beziehe ich mich nicht auf die Version des Algorithmus, wie Lipton sie beschreibt, sondern wie sie im ersten Kommentar (und im Buch von Kleinberg und Tardos) beschrieben wird.

Sasho Nikolov

Nur in Erwartung, siehe Domotorps Antwort.

Raphael

Ich sehe nirgendwo, dass Sie sich auf deterministische Algorithmen beschränken wollten. Der Algorithmus von rabin ist gerade deshalb interessant, weil er die unteren Grenzen des Entscheidungsbaums umgeht (dies ähnelt den unteren Grenzen für Vergleichssortierungs- und ganzzahlige Sortieralgorithmen). Übrigens gibt es wahrscheinlich mehr, das Rabin verwendet, um die Untergrenze zu umgehen, nämlich den Hashing-Trick, mit dem auf das Gitter zugegriffen wird

Sasho Nikolov,

Bezüglich des "Mehr, das Rabin verwendet": auch die Fähigkeit, reelle Zahleneingaben auf ganze Zahlen zu runden. Dabei muss man sehr vorsichtig sein: Wenn Sie ein Berechnungsmodell einrichten, in dem Standardarithmetikoperationen und Rundungen auf reelle Zahlen in konstanter Zeit pro Operation ausgeführt werden können, können PSPACE-vollständige Probleme in Polynomzeit gelöst werden in diesem Modell. Rabin rundet jedoch nur eingegebene Zahlen (mit unterschiedlicher Genauigkeit in unterschiedlichen Iterationen), und diese umschriebene Form der Rundung ist nicht problematisch.

David Eppstein

@SashoNikolov Ich habe nach der Worst-Case- Zeit in gesucht , also auch nach Worst-Case- in Frage 2. Dies hat nichts damit zu tun, ob der Algorithmus deterministisch ist. Ich bin mir nicht sicher, was passiert, wenn Sie die erwartete und die amortisierte Zeit kombinieren.

o (n \log n)

$o(n \log n)$

O (1)

$O(1)$

Raphael