late 1999 to early 2000 (and backfills for previous years) / DB reference years
PREV and NEXT link to numerically adjacent references for this DATABASE UPDATE.
CONTENTS links to the title list for this UPDATE's references.
Author Agarwal, Pankaj K. Desikan, Pavan K. Institution Duke Univ, Durham, NC, USA
Source Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. p 528-537. Conference Information 11th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco, CA, USA. 19000109-19000111.
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 epsilon greater than 0, we present an O((n/ epsilon 3)polylog n) algorithm that computes a build direction so that the total area of faces in contact with supports is at most (1 plus epsilon )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 Omega (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 omega , epsilon greater than 0, we present an algo rithm that computes a (1 plus epsilon )-approximate weighted omega -level in an arrangement of n weighted lines in time O((n/ epsilon 3) polylog n). (Auth abstract) [References: 28] XX