Math @ Duke

Publications [#235425] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Desikan, PK, Approximation algorithms for layered manufacturing,
in Eleventh Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2000),
pp. 528537
(last updated on 2018/10/18)
Abstract: 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 nonconvex 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).


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

