Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


28. Probleme des nächsten Punktes



Das Problem des nächsten Paares

Das Problem des nächsten Paares besteht darin, in einer Menge von Punkten die beiden Punkte zu finden, die am nächsten beieinander liegen. Dieses Problem ist mit dem Problem des nächsten Nachbarn verwandt; obwohl es nicht so weitverbreitete Anwendungsmöglichkeiten besitzt, wird es uns doch als Prototyp für das Problem des nächsten Punktes von Nutzen sein, da es mit Hilfe eines Algorithmus gelöst werden kann, dessen allgemeine rekursive Struktur für andere Probleme geeignet ist.

Man könnte meinen, daß es erforderlich sei, die Abstände zwischen allen Paaren von Punkten zu betrachten, um den kleinsten derartigen Abstand zu ermitteln; für N Punkte würde dies eine zu N2 proportionale Laufzeit bedeuten. Es erweist sich jedoch, daß wir Sortierverfahren anwenden können und dadurch mit der Untersuchung von nur ungefähr N log N Abständen zwischen Punkten im ungünstigsten Fall (weit weniger im durchschnittlichen Fall) auskommen und eine Laufzeit erhalten, die im ungünstigsten Fall proportional zu N log N ist (weit besser im durchschnittlichen Fall). Im vorliegenden Abschnitt untersuchen wir einen solchen Algorithmus ausführlich.

Der Algorithmus, den wir benutzen wollen, beruht auf einer sehr einfachen Strategie vom Typ »Teile und Herrsche«. Die Idee besteht darin, die Punkte bezüglich einer Koordinate, etwa der x-Koordinate, zu sortieren und dann diese Ordnung zu benutzen, um die Menge der Punkte in zwei Hälften zu zerlegen. Das nächste Paar in der gesamten Menge ist entweder das nächste Paar in einer der Hälften oder das nächste Paar unter den Paaren mit je einem Punkt in jeder Hälfte. Der interessante Fall ist natürlich der, wo das nächste Paar die Trennlinie kreuzt; das nächste Paar in jeder Hälfte kann offensichtlich durch Anwendung von rekursiven Aufrufen gefunden werden, doch wie können alle Paare mit Punkten beiderseits der Trennlinie in effizienter Weise geprüft werden?

Da die einzige Information, die wir benötigen, das nächste Paar in der Punktmenge ist, brauchen wir nur Punkte innerhalb eines Abstands min von der Trennlinie zu prüfen, wobei min der kleinere der Abstände zwischen den in den beiden Hälften gefundenen nächsten Paaren ist. Diese Bemerkung für sich allein ist im ungünstigsten Fall jedoch nicht ausreichend, da es viele Paare von Punkten geben könnte, die sehr nahe bei der Trennlinie liegen; zum Beispiel könnten in jeder Hälfte alle Punkte unmittelbar neben der Trennlinie aufgereiht sein.

Um solche Situationen zu behandeln, scheint es notwendig zu sein, die Punkte nach y zu sortieren. Dann können wir die Anzahl der für jeden Punkt erforderlichen Abstandsberechnungen wie folgt begrenzen: Durchlaufe die Punkte in steigender y-Reihenfolge und prüfe dabei, ob sich der jeweilige Punkt innerhalb des vertikalen Streifens befindet, der alle Punkte der Ebene mit einem Abstand von weniger als min von der Trennlinie enthält. Berechne für jeden solchen Punkt den Abstand zwischen ihm und jedem ebenfalls in dem Streifen befindlichen Punkt, dessen y-Koordinate kleiner als die y-Koordinate des aktuellen Punktes ist, jedoch nicht um mehr als min kleiner. Die Tatsache, daß der Abstand zwischen allen Paaren von Punkten in jeder Hälfte wenigstens min beträgt, hat zur Folge, daß wahrscheinlich nur wenige Punkte geprüft werden müssen.

Bei der kleinen Punktmenge auf der linken Seite von Abbildung 28.1 liegen acht Punkte links und acht Punkte rechts von der unmittelbar rechts neben F verlaufenden imaginären vertikalen Trennlinie. Das nächste Paar innerhalb der linken Hälfte ist AC (oder AO), das nächste Paar auf der rechten Seite ist JM. Wenn die Punkte nach y sortiert werden, wird das nächste durch die Trennlinie aufgespaltene Paar durch Prüfen der Paare HI, CI, FK (nächstes Paar in der gesamten Punktmenge) und schließlich EK gefunden. Für umfangreichere Punktmengen ist der die Trennlinie umgebende Streifen, der ein nächstes Paar enthalten könnte, schmaler, wie im rechten Teil von Abbildung 28.1 dargestellt ist.

Abbildung 28.1
Abbildung 28.1 Vorgehensweise nach der Methode »Teile und Herrsche« zum Auffinden des nächsten Paares.

Obwohl sich dieser Algorithmus einfach formulieren läßt, ist eine gewisse Sorgfalt erforderlich, um ihn effizient zu implementieren: Zum Beispiel wäre es zu aufwendig, die Punkte innerhalb unseres rekursiven Unterprogramms nach y zu sortieren. Wir haben verschiedene Algorithmen mit Laufzeiten kennengelernt, die durch die rekurrente Beziehung CN = 2CN/2 + N beschrieben werden, welche zur Folge hat, daß CN proportional zu N log N ist; wenn wir das vollständige Sortieren nach y vornehmen würden, würde die rekurrente Beziehung die Form CN = 2CN/2 + N log N erhalten, was zur Folge hätte, daß CN proportional zu N log2 N wäre (siehe Kapitel 6). Um dies zu vermeiden, müssen wir das Sortieren nach y umgehen.

Die Lösung für dieses Problem ist einfach, aber subtil. Das Verfahren Mergesort aus Kapitel 12 beruht auf einer Aufteilung der zu sortierenden Elemente, die in genau der gleichen Weise vorgenommen wird, in der oben die Punkte aufgeteilt werden. Wir haben zwei zu lösende Probleme und das gleiche allgemeine Verfahren für ihre Lösung, daher können wir sie ebensogut gleichzeitig lösen! Wir wollen also eine rekursive Routine erstellen, die sowohl nach y sortiert als auch das nächste Paar findet. Sie löst diese Aufgabe, indem sie die Punktmenge aufspaltet, sich dann selbst rekursiv aufruft, um die beiden Hälften nach y zu sortieren und das nächste Paar in jeder Hälfte zu finden, danach mischt, um das Sortieren nach y zu vollenden, und die obige Prozedur anwendet, um die Berechnung des nächsten Paares zu vollenden. Auf diese Weise vermeiden wir den Aufwand eines zusätzlichen Sortierens nach y, indem wir die für das Sortieren erforderliche Umordnung der Daten mit den für die Berechnung des nächsten Paares erforderlichen Datenmanipulationen mischen.

Für das Sortieren nach y könnte das Aufspalten in beliebiger Weise vorgenommen werden, doch für die Berechnung des nächsten Paares ist es notwendig, daß die Punkte in der einen Hälfte kleinere x-Koordinaten haben als die Punkte in der anderen Hälfte. Das läßt sich leicht erreichen, indem man vor Ausführung der Zerlegung nach x sortiert. In Wirklichkeit können wir genausogut die gleiche Routine für das Sortieren nach x verwenden! Nachdem dieses allgemeine Schema festgelegt ist, ist die Implementation nicht schwer zu verstehen.

Wie bereits erwähnt wurde, werden für die Implementation die rekursiven Prozeduren sort und merge aus Kapitel 12 verwendet. Der erste Schritt besteht darin, die Strukturen der Listen dahingehend zu modifizieren, daß sie Punkte anstelle von Schlüsseln enthalten, und merge so zu modifizieren, daß eine globale Variable pass geprüft wird, um zu entscheiden, wie der Vergleich vorgenommen wird. Falls pass = 1 gilt, sind die x-Koordinaten der beiden Punkte zu vergleichen; falls pass = 2 ist, vergleichen wir die y-Koordinaten der beiden Punkte. Die zugehörige Implementation ist sehr einfach:

    function merge(a,b: link): link;
      var c: link; comp: boolean;
      begin
      c:=z;
      repeat
        if pass=1 
          then comp:=a^.p.x<b^.p.x 
          else comp:=a^.p.y<b^.p.y 
        if comp 
          then begin c^.next:=a; c:=a; a:=a^.next end
          else begin c^.next:=b; c:=b; b:=b^.next end
      until c=z;
      merge:=z^.next; z^.next:=z;
      end;

Der Pseudoknoten z, der am Ende aller Listen erscheint, wird so initialisiert, daß er einen »Marken«-Punkt mit künstlich großen Koordinaten x und y enthält.

Um Abstände zu berechnen, verwenden wir eine andere einfache Prozedur, die prüft, ob der Abstand zwischen den beiden als Parameter angegebenen Punkten kleiner ist als die globale Variable min. Wenn dies der Fall ist, setzt sie min auf den Wert dieses Abstands und speichert die Punkte in den globalen Variablen cp1 und cp2:

    procedure check(p1,p2: point);
      var dist: real;
      begin
      if (p1.y<>z^.p.y) and (p2.y<>z^.p.y) then
        begin
        dist:=sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
        if dist<min then
          begin min:=dist; cp1:=p1; cp2:=p2 end;
        end;
      end;

Somit enthält die globale Variable min immer den Abstand zwischen cp1 und cp2, dem nächsten bisher gefundenen Paar.

Der folgende Schritt besteht darin, das rekursive Sortieren aus Kapitel 12 gleichfalls zu modifizieren, damit die Berechnung des nächsten Punktes ausgeführt wird, wenn pass = 2 gilt:

    function sort(c: link; N: integer): link;
      var a,b: link; i: integer;
          middle: real;
          p1,p2,p3,p4: point;
      begin
      if c^.next=z then sort:=c else
        begin
        a:=c;
        for i:=2 to N div 2 do c:=c^.next;
        b:=c^.next; c^.next:=z;
        if pass=2 then middle:=b^.p.x;
        c:=merge(sort(a,N div 2),sort(b,N-(N div 2)));
        sort:=c;
        if pass=2 then
          begin
          a:=c; p1:=z^.p; p2:=z^.p; p3:=z^.p; p4:=z^.p;
          repeat
            if abs(a^.p.x-middle)<min then
              begin
              check(a^.p,p1);
              check(a^.p,p2);
              check(a^.p,p3);
              check(a^.p,p4);
              p1:=p2; p2:=p3; p3:=p4; p4:=a^.p
              end;
            a:=a^.next
          until a=z
          end
        end;
      end;

Falls pass = 1 ist, ist dies genau die rekursive Routine für Mergesort aus Kapitel 12; sie gibt eine verkettete Liste zurück, die die nach ihren x-Koordinaten sortierten Punkte enthält (da merge in der oben beschriebenen Weise modifiziert wurde, um beim 1. Durchlauf x-Koordinaten zu vergleichen). Der Glanzpunkt dieser Implementation kommt, wenn pass = 2 gilt. Das Programm sortiert nicht nur nach y (da merge in der oben beschriebenen Weise modifiziert wurde, um beim 2. Durchlauf die y-Koordinaten zu vergleichen), sondern es vollendet auch die Berechnung des nächsten Punktes, wie weiter unten ausführlich beschrieben wird.

Zuerst sortieren wir nach x; dann sortieren wir nach y und finden das nächste Paar, indem wir sort wie folgt aufrufen:

    new(z); z^.next:=z;
    z^.p.x:=maxint; z^.p.y:=maxint;
    new(h); h^.next:=readlist;
    min:=maxint;
    pass:=1; h^.next:=sort(h^.next,N);
    pass:=2; h^.next:=sort(h^.next,N);

Nach diesen Aufrufen ist das nächste Paar von Punkten in den globalen Variablen cp1 und cp2 zu finden, die mittels der Prozedur check »Auffinden des Minimums« verwaltet werden.

Das entscheidende Merkmal der Implementation ist die Art der Anwendung von sort, wenn pass = 2 gilt. Vor den rekursiven Aufrufen sind die Punkte nach x sortiert; diese Ordnung wird benutzt, um die Punktemenge in zwei Hälften zu zerlegen und die x-Koordinate der Trennlinie zu finden. Nach den rekursiven Aufrufen sind die Punkte nach y sortiert, und es ist bekannt, daß der Abstand zwischen jedem Paar von Punkten in jeder Hälfte größer als min ist. Das Ordnen nach y wird benutzt, um die nahe der Trennlinie befindlichen Punkte zu durchmustern; der Wert von min wird verwendet, um die Anzahl der zu prüfenden Punkte zu begrenzen. Jeder Punkt, dessen Abstand von der Trennlinie kleiner als min ist, wird mit Hilfe von check mit jedem der vorangegangenen vier Punkte verglichen, die in einem Abstand von weniger als min von der Trennlinie gefunden wurden. Durch diese Prüfung wird garantiert, daß jedes Paar von Punkten mit jeweils einem Punkt auf jeder Seite der Trennlinie gefunden wird, das näher beieinander liegt als min. (Dies ist eine interessante geometrische Tatsache, die der Leser nachprüfen kann: Wir wissen, daß Punkte, die sich auf der gleichen Seite der Trennlinie befinden, wenigstens den Abstand min voneinander haben, daher ist die Anzahl der Punkte, die sich innerhalb eines Kreises mit dem Radius min befinden können, begrenzt.)

Abbildung 28.2 zeigt den Baum der rekursiven Aufrufe, der die Arbeitsweise dieses Algorithmus für unsere kleine Punktmenge zeigt. Ein innerer Knoten in diesem Baum stellt eine vertikale Linie dar, die die Punkte im linken und rechten Teilbaum voneinander trennt. Die Knoten sind in der Reihenfolge numeriert, in der die vertikalen Linien von dem Algorithmus geprüft werden. Diese Numerierung entspricht einer Postorder-Traversierung des Baumes, da die Berechnung, in der die Trennlinie eine Rolle spielt, nach den rekursiven Aufrufen im Programm kommt; sie ist einfach eine andere Betrachtungsweise der Reihenfolge, in der während eines rekursiven Mergesorts die Mischoperationen ausgeführt werden (siehe Kapitel 12).

Abbildung 28.2
Abbildung 28.2 Baum der rekursive Aufrufe für die Berechnung des nächsten Paares.

Demzufolge wird zuerst die Verbindung zwischen G und O geprüft, und das Paar GO wird als das bisher nächste gespeichert. Dann wird die Verbindung zwischen A und D getestet, doch A und D liegen zu weit auseinander, um min zu ändern. Danach wird die Verbindung zwischen O und A geprüft, und die Paare GD, GA und OA stellen nacheinander jeweils nähere Paare dar. Dann werden bis zum Auftreten von FK, welches das letzte geprüfte Paar für die letzte getestete Trennlinie ist, keine näheren Paare gefunden.

Der aufmerksame Leser wird bemerkt haben, daß wir nicht den oben beschriebenen reinen Algorithmus vom Typ »Teile und Herrsche« implementiert haben; in Wirklichkeit berechnen wir nicht das nächste Paar in den beiden Hälften und nehmen dann das bessere von beiden. Stattdessen erhalten wir das nähere der beiden nächsten Paare einfach dadurch, daß wir während der rekursiven Berechnung eine globale Variable für min benutzen. Jedesmal, wenn wir ein näheres Paar finden, können wir einen schmaleren vertikalen Streifen um die aktuelle Trennlinie herum betrachten, unabhängig davon, wo wir uns bei der rekursiven Berechnung befinden.

Abbildung 28.3 zeigt den Prozeß im einzelnen. Die x-Koordinate in diesen Schemata wurde vergrößert, um die Orientierung des Prozesses auf x zu unterstreichen und Parallelen zu Mergesort (siehe Kapitel 12) sichtbar zu machen. Wir beginnen damit, daß wir ein Sortieren nach y für die vier am weitesten links befindlichen Punkte G O A D vornehmen, indem wir G O sortieren, dann A D sortieren und dann mischen. Nach dem Mischen ist das Sortieren nach y beendet, und wir finden das nächste Paar AO, das sich beiderseits der Trennlinie befindet. Schließlich sind die Punkte nach ihren y-Koordinaten sortiert, und das nächste Paar ist berechnet.

Abbildung 28.3
Abbildung 28.3 Berechnung des nächsten Paares (x-Koordinate vergrößert).

Eigenschaft 28.1 Das nächste Paar in einer Menge von N Punkten kann in O(N log N) Schritten gefunden werden.

Im wesentlichen wird die Berechnung in der Zeit ausgeführt, die benötigt wird, um zwei Mergesorts (einen für die x-Koordinate und einen für die y-Koordinate) auszuführen; hinzu kommt der Aufwand für die Suche entlang der Trennlinie. Auch dieser Aufwand wird durch die rekurrente Beziehung TN = TN/2 + N bestimmt (siehe Kapitel 6). w.z.b.w.

Der allgemeine Ansatz, den wir hier für das Problem des nächsten Paares benutzt haben, kann verwendet werden, um andere geometrische Probleme zu lösen. Eine andere Frage, die von Interesse ist, ist zum Beispiel das Problem aller nächsten Nachbarn: Für jeden Punkt möchten wir denjenigen Punkt finden, der ihm am nächsten liegt. Dieses Problem kann gelöst werden, indem ein Programm von der Art des obigen benutzt wird, mit einem zusätzlichen Durchsuchen entlang der Trennlinie, um für jeden Punkt festzustellen, ob ein Punkt auf der anderen Seite vorhanden ist, der näher ist als der ihm nächstgelegene Punkt auf der eigenen Seite. Auch für diese Berechnung ist wiederum das »freie« Sortieren nach y von Nutzen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]