Punkteinfuegen d and c
Polopower
Beim Einfügen von P sind nur die bereits vorhandenen Punkte des grünen bzw. blauen Rechtecks zu prüfen. Erstellt man eine nach y-Werten sortierte Liste S an Punkten, welche x-Entfernung <δ von der roten Trenngrenze haben (in O(n) möglich), so sind also nach oben und unten nur die jeweils 12 am nächsten von P liegenden Punkte aus S zu beachten. (Davon können sowieso nur die hier rechts der Grenze liegenden Punkte δ unterbieten; daß die auf der Seite von P liegenden dies nicht tun ist der Effekt des Algorithmus, da δ extra so berechnet wurde.) Bereits Punkt Q wäre Nr. 13 in S, und ist somit unbeachtlich.
selbst erstellt
Relevante Bilder
Relevante Artikel
Dichtestes PunktpaarDas Problem des dichtesten Punktpaares ist die Suche nach den zwei am dichtesten beieinander liegenden Punkten in einer Ebene. Gegeben ist eine beliebige Menge von Punkten in der Ebene und gesucht sind zwei dieser Punkte, sodass der euklidische Abstand minimal ist. Ein ähnliches Problem ist die Suche nach den zwei am weitesten voneinander entfernten Punkten in der Ebene, also den zwei Punkten mit dem maximalen euklidischen Abstand. .. weiterlesen