Try changing the configuration by
clicking in the diagram! Try changing the regions by dragging
the colored points! The Rotation Diagram (in the bottom half of the picture below) represents all configurations (rotations and translations) of the black polygon that keep the polygon in contact with the gray point.
The horizontal axis of the diagram represents the rotations, while the vertical axis represents the translations along the circumference of the polygon. The colored regions in the diagram correspond to configurations of the polygon which contain the point of the same color. Thus, the diagram "wraps around", both left-right and top-bottom.
Try changing the configuration by
clicking in the diagram!
Try changing the regions by dragging
the colored points!
Change the number of points and the polygon with the buttons. If the "3-gon" choice button doesn't seem to work, try reloading the page and/or clicking the button in different places.
Turning on the "circles" button and then moving the colored points illustrates that the shape of the regions in the Rotation Diagram is independent of the angle. Turning on the "polys" button and changing the rotation (moving the point along the bottom of the diagram) illustrates that the critical events in the diagram correspond to the intersections of edges with vertices when two copies of the polygon rotate in tandem.
What are Rotation Diagrams (RDs) good for? They can help us to quickly solve the Polygon Placement Problem: Given a convex polygon and a number of points in the plane, we want to find the placement of the polygon that covers the most points.
The basic idea is that we only have to look for placements in which the polygon touches one of the points (because for any maximizing placement, we can slightly move the polygon so that it touches a point). Thus, we do the following: For each point, we let this point be the fixed (gray) point and we compute the RD with respect to all other (colored) points. We then find the point of maximum overlap of the colored regions. Among all RDs, we pick the diagram with the deepest overlap, corresponding to a placement in which the polygon touches one point and covers the highest number of all other points. Voila!
It turns out that the Rotation Diagrams can be computed efficiently, and that the overall best placement can be found found in O(n k^2 m^2 log(mk)) time, where n is the number of points, m is the number of vertices, and k is the depth of the overlap, i.e. the maximum number of points contained. This provides a linear improvement over the best previously known algorithm when k is large and a cubic improvement when k is small. If you are interested in more details, please see our paper:
The Source (fairly messy... ;-)