Approximation algorithms for layered manufacturing
An important problem in layered manufacturing is the choice of a good build direction, which influences the quality and the cost of manufacturing the object. We present efficient algorithms for computing a build direction that optimizes the total area of faces that are in contact with supports. For a given convex polytope with n faces and for a parameter ε>0, we present an O((n/ε3)polylog n) algorithm that computes a build direction so that the total area of faces in contact with supports is at most (1+ε)A*, where A* is the minimum area of contact with supports for all build directions. For non-convex polyhedra, we provide evidence that the lower bound for any algorithm computing the optimal direction might be Ω(n4). We also present a faster algorithm for some special cases. Our technique for convex polyhedra involves computing approximate levels in arrangement of lines with weights. For given parameters ω,ε>0, we present an algorithm that computes a (1+ε)-approximate weighted ω-level in an arrangement of n weighted lines in time O((n/ε3) polylog n).
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page