Closest Punktepaar

Question

In http://en.wikipedia.org/wiki/Closest_pair_of_points_problem können wir sehen, dass es, dass erwähnt höchstens 6 Punkte, die am nächsten zu dem Punkt, auf der anderen Hälfte ist, die als Grafik unten dargestellt werden können:

Mein Frage ist für Punkt P1 und Punkt P2, der Abstand zum roten Punkt wird größer als sqrt (2) * d, warum ist es ein Teil der Lösung? Warum sind es höchstens 4 Punkte, die eher P als höchstens 6 Punkten entsprechen? Vielen Dank.

Answer 1

P1 und P2 sind nicht Teil der Lösung, aber sie haben auf dem Weg zur Lösung untersucht werden, da der Algorithmus alle Punkte in der Box untersucht, und P1 und P2 sind in der BOx.

anzumerken, dass kein solcher Punkt als Q kann, weil durch Hypothese existieren, den Mindestabstand zwischen den Punkten in der rechten Hälfte des Diagramms ist d.

Edited hinzufügen: Sie scheinen zu denken, dass der Wikipedia-Artikel ist ein Anspruch wie folgt machen:

• Es kann bis zu 6 Punkte auf der rechten Seite der Linie sein, die in einem Abstand d von P.

Dieser Anspruch wäre falsch. Aber der Artikel macht keinen solchen Anspruch. Stattdessen macht es zwei getrennte Ansprüche, welche beide erfüllt sind:

1. alle Punkte auf der rechten Seite der Linie, die in einem Abstand d von P sind innerhalb der Box sind.
2. Es kann bis zu 6 Punkte in der Box geben.

Answer 2

Wir zählen nur die maximale Anzahl der Punkte, die im rechten d x 2d Rechteck liegen können. Da alle zwei Punkte auf einen Mindestabstand von d beschränkt sind, können wir maximal 6 Punkte im Rechteck platzieren, während wir diese Einschränkung erfüllen, wie in der Abbildung gezeigt.

Beachten Sie, dass die Punkte auf der rechten Seite, die innerhalb von d Abstand von P liegen, alle innerhalb eines Kreissegments eines Kreises liegen sollten, der bei P zentriert ist und dessen Radius d ist. In diesem Segment kann es maximal 4 Punkte geben. Es ist jedoch komplizierter, die Anzahl der Punkte innerhalb eines Segments zu finden, als die Anzahl der Punkte innerhalb eines Rechtecks ​​zu finden. Wir verwenden stattdessen das Rechteck und verursachen zusätzliche Kosten für die Suche nach höchstens 2 zusätzlichen Punkten.

Answer 3

Die Schranke für die Komplexität Schätzung nur wichtig ist. Codeweise können Sie einfach innerhalb der Distanz dRmin nach oben und unten scannen. Die Grenze hier deutet darauf hin, dass Sie höchstens 6 Punkte in jedem solchen Scan sehen werden, macht dies O (1).