Algorithms for designing clamshell molds

Clamshell casting is a popular manufacturing technique where liquid is poured into a mold or cast and the cast is removed once the liquid has hardened. The term clamshell refers to the way in which the cast is removed. The two cast parts are removed by rotation through a hinge much like a clamshell. Given an object, modeled by a polyhedron P of arbitrary genus with combinatorial complexity n , we determine when the surface of the polyhedron can be decomposed into two parts s.t. each part can be rotated around a line in space without colliding with each other or intersecting the interior. Such a line is a valid casting line. Specifically, we solve the following problems: (1) Given a line l in space, we determine in O(n) time whether l is a valid casting line for P . If degeneracies are present, such as a reflex edge or face of P is perpendicular to l, the running time increases slightly to O(n log n). (2) In O(n 4α(n)) time, where α(n) is the inverse Ackermann function, we report all combinatorially distinct valid casting lines. The running time is O(n4 log n) in the presence of degeneracies. All of the running times are shown to be almost optimal.