Bewegung einer Leiter in 2 Dimensionen
- Visualisierung einer unteren Schranke

Applet wird gestartet... [Applet kann nicht gestartet werden]

Das Applet visualisiert ein Szenario, das aus Polygonen mit einer Gesamtanzahl von n Knoten konstruiert wurde und für eine Leiter fester Länge die Bewegung von einem bekanntem Startpunkt zu einem bekannten Zielpunkt zulässt. Dabei darf die Leiter die Polygone, die in diesem Falle Hindernisse darstellen nicht überspringen.

Beim gegebenen Szenario wird eine Mindestzahl von Ω(n2) Bewegungen benötigt, um die Leiter von ihrer Startposition zwischen den ersten beiden Hindernissknoten der A- und B-Reihe zu ihrer Zielposition zwischen den letzten beiden Hindernissknoten der A- und B-Reihe zu bewegen. Gezählt werden dabei Rotationen und Translationen als jeweils ein Schritt.

Mögliche Mausaktionen sind:

 

  • durch einen Linksklick auf einen der Eckpunkte der Leiter lässt sich die Leiter um den anderen Eckpunkt rotieren
  • durch einen Rechtsklick auf einen der Eckpunkte der Leiter wird diese um das verschiebbare Rotationszentrum rotiert
  • durch einen Linksklick auf das Liniensegment zwischen den beiden Endpunkten der Leiter kann diese entlang ihrer aktuellen Ausrichtung nach oben bzw. unten bewegt werden
  • durch einen Rechtsklick auf das Liniensegment zwischen den beiden Endpunkten der Leiter kann diese zweidimensional bei Beibehaltung der Orientierung verschoben werden.
  • durch Drehen des Mausrades kann die Leiter gemäß ihrer aktuellen Orientierung maximal nach oben bzw. unten verschoben werden, gemäß der Drehrichtung des Mausrades
  • durch einfaches Ziehen lässt sich das Rotationszentrum verschieben (dies kostet natürlich keine Schritte)

Beispiel:

 

Quellen:

[1] Y. Ke, J. O'Rourke. Moving a ladder in three dimensions: upper and lower bounds. 1987.

    siehe: ACM Portal (Hinweis: Sie benötigen einen kostenpflichtigen Account)