1
$\begingroup$

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 - Rotation from 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?

$\endgroup$
4
$\begingroup$

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

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$ - pivot rotation direction

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 - enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. May 1 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.