Optimal Algorithms for Separating a Polyhedron from its Single-Part Mold

Abstract

Casting is a manufacturing process where liquid material is poured into a mold having the shape of a desired product. After the material solidifies, the product is removed from the mold. We study the case where the mold is made of a single part and the object to be produced is a three-dimensional polyhedron. Objects that can be produced this way are called castable with a single-part mold. A direction in which the object can be removed without breaking the mold is called a valid removal direction. We give an O(n)-time algorithm that decides whether a given polyhedron with n facets is castable with a single-part mold. When possible, our algorithm provides an orientation of the polyhedron in the mold and a direction in which the product can be removed without breaking the mold. Moreover, we provide an optimal Θ(n log n)-time algorithm to compute all valid removal directions for polyhedra that are castable with a single-part mold. Both algorithms are an improvement by a linear factor over the previously best known algorithms for both of these problems. We also present an exact implementation of our algorithms using the CGAL library and employ our implementation to demonstrate the castability of a variety of polyhedra.