# Polygon casting - Removing from mold by rotation

The following question appears in Section 4.9 of "Computational Geometry: Algorithms and Applications" By Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf:

Show that the problem of finding a center of rotation that allows us to remove $$P$$ with a single rotation from its mold can be reduced to the problem of finding a point in the common intersection of a set of half-planes.

$$P$$ here is a simple polygon with a given orientation, cast in a mold -

Whether $$P$$ can be removed with a translation can be reduced to whether a common intersection of a set of half-planes is unbounded: Each edge of $$P$$, continued to a line, defines the half plane touching the outer side of the edge. The intersection of these half-planes is unbounded in a direction $$\vec{v}$$ if and only if translating $$P$$ by $$\vec{v}$$ does not cause any edge to push against the mold.

How can this reduction be modified to solve the case of removing $$P$$ with a rotation around a point?

Consider the marked edge of the following object (light gray) in its mold (dark gray) -

Where must $$p$$ be such that an arbitrary points on the edge will not be pushed against the mold? This figure shows the direction a point on the edge will be moving in when rotated around a point $$p$$ -

Notice that the point will be moving perpendicular to the line connecting it with $$p$$. Now recall that in order not to push on the mold, the points of the edge must move in the direction of the inner half-plane defined by the edge. This means that the possible locations for $$p$$ lie on a half-plane perpendicular to the edge. Here's the half-plane (in green) corresponding to an inner point of the edge -

The half-plane corresponding to the upper vertex of the edge, in this case, is contained in all of the half-planes for inner points, and so a rotation around any point in it moves the entire edge such that it does not push on the mold.

Whether $$P$$ can be removed with a rotation around $$p$$, is thus equivalent to whether $$p$$ is in the common intersection of the half-planes defined by $$P$$'s edges.

• Welcome to CS.SE! Thank you for the detailed answer and edit to the question! I hope you'll stick around and continue to contribute.
– D.W.
May 1, 2019 at 4:59