Moving a Ladder in Two
Dimensions
- Visualization of a Lower Bound
Starting applet...
The purpose of this applet is to visualize a lower bound for any
algorithm to compute a sequence of motions to move a ladder from a given
source position to a given destination without penetrating known
polygonial obstacles with a total of n vertices.
The computed scenario forces any algorithm to do not less than Ω(n2)
movements (these are rotations and translations) in order to move the ladder along shortest
path to reach its final position.
Possible actions are:
a left-click on one of the two vertices of
the ladder rotates this vertex around the other
a right-click on one of the vertices rotates
the ladder around a moveable rotation-centre
a left-click on the segment between the two in one dimension
along the current direction limiting vertices of the ladder will move it
a right-click on the segment between the two
limiting vertices of the ladder will move it
in two dimensions along the current direction
the mouse-wheel can be used to perform the
maximum movement possible along the current
direction according to the direction the mouse-wheel
the rotation-centre can be moved by dragging
the polygon
Example:
References:
[1] Y. Ke, J. O'Rourke.
Moving a ladder in three dimensions:
upper and lower bounds. 1987.
siehe: ACM Portal
(note: you need an account to download the article)
