FILLING POLYHEDRAL MOLDS

In manufacturing industry, finding an orientation for a mold that elim inates surface defects and ensures a complete fill after termination o f the gravity casting process is an important and difficult problem. W e study the problem of determining a favorable position of a mold (mod eled as a polyhedron) such that, when it is filled, no air pockets and ensuing surface defects arise. Given a polyhedron in a fixed orientat ion, we present a linear time algorithm that determines whether the mo ld can be filled from that orientation without forming air pockets. We also present an algorithm that determines the most favorable orientat ion for a polyhedral mold in O(n(2)) time. A reduction from a well-kno wn problem indicates that improving the O(n(2)) bound is unlikely for general polyhedral molds. We relate fillability to some well known cla sses of polyhedra. For some of these classes of objects, an optimal di rection of fillability can be determined in linear time. Finally, for molds that satisfy a local regularity condition, we give an improved a lgorithm that runs in time O(nklog(2) nlog log(n/k)), where k is the n umber of venting holes needed to avoid air pockets in an optimal orien tation. (C) 1998 Published by Elsevier Science Ltd. All rights reserve d.