Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235425] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Desikan, PK, Approximation algorithms for layered manufacturing, in Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 528-537
    (last updated on 2018/10/18)

    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).
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320