Robert Sedgewick: Algorithmen

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


25. Bestimmung der konvexen Hülle



Übungen

  1. Angenommen, es ist im voraus bekannt, daß die konvexe Hülle einer Punktmenge ein Dreieck ist. Geben Sie einen einfachen Algorithmus zur Bestimmung des Dreiecks an. Lösen Sie die gleiche Aufgabe für ein Viereck.
  2. Geben Sie ein effizientes Verfahren an, mit dem bestimmt werden kann, ob ein Punkt innerhalb eines gegebenen konvexen Polygons liegt.
  3. Implementieren Sie unter Benutzung Ihres Verfahrens aus der vorangegangenen Übung einen Algorithmus zur Bestimmung der konvexen Hülle von der Art von insertion sort.
  4. Ist es für das Durchsuchen nach Graham unbedingt erforderlich, mit einem Punkt zu beginnen, der garantiert auf der Hülle liegt? Erklären Sie, warum oder warum nicht.
  5. Ist es für das Einwickel-Verfahren unbedingt erforderlich, mit einem Punkt zu beginnen, der garantiert auf der Hülle liegt? Erklären Sie, warum oder warum nicht.
  6. Skizzieren Sie eine Punktmenge, für die das Durchsuchen nach Graham zur Bestimmung der konvexen Hülle besonders ineffizient wird.
  7. Liefert das Durchsuchen nach Graham die konvexe Hülle der Punkte, die die Ecken eines beliebigen einfachen Polygons darstellen? Erklären Sie, warum, oder geben Sie ein Gegenbeispiel an, das zeigt, warum nicht.
  8. Welche vier Punkte sollten für das Verfahren der inneren Elimination verwendet werden, wenn die Eingabedaten als innerhalb eines Kreises zufällig verteilt angenommen werden (unter Verwendung zufälliger Polarkoordinaten)?
  9. Führen Sie einen empirischen Vergleich des Durchsuchens nach Graham und des Einwickel-Verfahrens für große Punktmengen durch, wobei sowohl x als auch y zwischen 0 und 1000 gleichverteilt sind.
  10. Implementieren Sie das Verfahren der inneren Elimination und bestimmen Sie empirisch, wie groß N sein sollte, bevor man erwarten kann, daß fünfzig Punkte übrigbleiben, nachdem das Verfahren auf Punktmengen angewandt worden ist, bei denen x und y zwischen 0 und 1000 gleichverteilt sind.


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