Robert Sedgewick: Algorithmen

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


28. Probleme des nächsten Punktes



Übungen

  1. Erstellen Sie Programme zur Lösung des Problems des nächsten Nachbarn, zuerst unter Anwendung des Gitterverfahrens, dann unter Anwendung von 2D-Bäumen.
  2. Beschreiben Sie, was geschieht, wenn die Prozedur des nächsten Paares auf eine Menge von äquidistanten Punkten angewandt wird, die alle auf ein und derselben horizontalen Linie liegen.
  3. Beschreiben Sie, was geschieht, wenn die Prozedur des nächsten Paares auf eine Menge von äquidistanten Punkten angewandt wird, die alle auf ein und derselben vertikalen Linie liegen.
  4. Geben Sie einen Algorithmus an, der für eine gegebene Menge von 2N Punkten, von denen eine Hälfte positive und die andere Hälfte negative x-Koordinaten hat, das nächste Paar mit jeweils einem Punkt in jeder Hälfte auffindet.
  5. Geben Sie die aufeinanderfolgenden Paare von Punkten an, die cp1 und cp2 zugewiesen werden, wenn man das Programm aus diesem Kapitel für die Punkte aus dem Beispiel, jedoch nach Entfernen von A ablaufen läßt.
  6. Überprüfen Sie die Effizienz der Wahl von min als globalen Variablen, indem Sie für eine gewisse umfangreiche zufällige Punktmenge die Leistungsfähigkeit der angegebenen Implementation mit einer rein rekursiven Implementation vergleichen.
  7. Geben Sie einen Algorithmus für das Auffinden des nächsten Paares aus einer Menge von Strecken an.
  8. Zeichnen Sie das Voronoi-Diagramm und die zu ihm duale Struktur für die Punkte A B C D E F aus der Beispiel-Punktmenge.
  9. Geben Sie ein »grobes« Verfahren (welches eine zu N2 proportionale Zeit erfordern könnte) zur Berechnung des Voronoi-Diagramms an.
  10. Erstellen Sie ein Programm zum Auffinden der konvexen Hülle einer Menge von Punkten, in dem die gleiche rekursive Struktur benutzt wird wie in der in diesem Kapitel angegebenen Implementation für das nächste Paar.


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