TR-06-03: Rotational Clamshell Casting In Two Dimensions

Abstract

A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed once the liquid has hardened. We consider the case where the object to be manufactured is a simple polygon with n vertices in the plane. The cast consists of exactly two parts and is removed by a rotation around a point in the plane. The following two problems are addressed: (1) Given a cast and a center of rotation r in the plane, we determine in O(n) time whether there exists a partitioning of the cast into exactly two parts, such that one part can be rotated clockwise around r and the other part can be rotated counterclockwise around r without colliding with the interior of the polygon. (2) An algorithm is presented to find all the points in the plane that allow a cast partitioning as described above. For convex polygons, an algorithm with running time O(n) is presented. For simple polygons, the algorithm’s running time becomes O(n2).