Robert Sedgewick: Algorithmen

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


27. Geometrischer Schnitt



Übungen

  1. Wie würden Sie bestimmen, ob sich zwei Dreiecke schneiden? Quadrate? Regelmäßige n-Ecke für n > 4?
  2. Wie viele Paare von Linien in einer Linienmenge ohne Schnitte werden bei dem Algorithmus für den Schnitt horizontaler und vertikaler Linien im ungünstigsten Fall auf einen Schnitt geprüft? Fertigen Sie eine Skizze an, die Ihre Antwort belegt.
  3. Was geschieht, wenn die Prozedur für den Schnitt horizontaler und vertikaler Linien auf eine Menge von Strecken mit beliebiger Steigung angewandt wird?
  4. Erstellen Sie ein Programm zur Ermittlung der Anzahl sich schneidender Paare innerhalb einer Menge von N zufälligen horizontalen und vertikalen Linien, wobei jede Linie mit Hilfe von zwei zufälligen ganzzahligen Koordinaten zwischen 0 und 1000 und einem zufälligen Bit zur Unterscheidung zwischen horizontal und vertikal erzeugt wird.
  5. Geben Sie ein Verfahren an, mit dem geprüft werden kann, ob ein gegebenes Polygon einfach ist (sich nicht selbst schneidet).
  6. Geben Sie ein Verfahren an, mit dem geprüft werden kann, ob ein Polygon vollständig in einem anderen enthalten ist.
  7. Beschreiben Sie, wie Sie das allgemeine Problem des Schnitts von Strecken lösen würden, wenn die zusätzliche Tatsache gegeben ist, daß der minimale Abstand zwischen zwei Linien größer ist als die maximale Länge der Linien.
  8. Geben Sie die Binärbaum-Strukturen an, die vorliegen, wenn der Algorithmus für den Schnitt der Linien auf die Linien in Abbildung 27.6 angewandt wird, nachdem letztere um 90 Grad gedreht wurde.
  9. Sind die in diesem Kapitel beschriebenen Vergleichsprozeduren für Kreise und Manhattan-Rechtecke transitiv?
  10. Erstellen Sie ein Programm zum Auffinden der Anzahl sich schneidender Paare innerhalb einer Menge von N zufälligen Linien, wobei jede Linie mit Hilfe von zufälligen ganzzahligen Koordinaten zwischen 0 und 1000 erzeugt wird.


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