On some geometric optimization problems in layered manufacturing

Efficient geometric algorithms are given for optimization problems arising in layered manufacturing, where a 3D object is built by slicing its CAD mod el into layers and manufacturing the layers successively. The problems cons idered include minimizing the stair-step error on the surfaces of the manuf actured object under various formulations, minimizing the volume of the so- called support structures used, and minimizing the contact area between the supports and the manufactured object-all of which are factors that affect the speed and accuracy of the process. The stair-step minimization algorith m is valid for any polyhedron, while the support minimization algorithms ar e applicable only to convex polyhedra. The techniques used to obtain these results include construction and searching of certain arrangements on the s phere, 3D convex hulls, halfplane range searching, and constrained optimiza tion. (C) 1999 Elsevier Science B.V. All rights reserved.