Efficient geometric algorithms are given for optimization problems arising in layered manufacturing, where a 3D object is built by slicing its CAD model into layers and manufacturing the layers successively. The problems considered include minimizing the degree of stair-stepping on the surfaces of the manufactured object, 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 algorithm is valid for any polyhedron, while the support minimization algorithms are applicable to convex polyhedra only. Algorithms are also given for optimizing supports for non-convex, simple polygons. The techniques used include construction and searching of certain arrangements on the sphere, 3D convex hulls, halfplane range searching, ray-shooting, visibility, and constrained optimization.
|Original language||English (US)|
|Title of host publication||Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings|
|Editors||Frank Dehne, Jorg-Rudiger Sack, Andrew Rau-Chaplin, Roberto Tamassia|
|Number of pages||14|
|ISBN (Print)||3540633073, 9783540633075|
|State||Published - 1997|
|Event||5th International Workshop on Algorithms and Data Structures, WADS 1997 - Halifax, Canada|
Duration: Aug 6 1997 → Aug 8 1997
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||5th International Workshop on Algorithms and Data Structures, WADS 1997|
|Period||8/6/97 → 8/8/97|
Bibliographical noteFunding Information:
I Portions of this work appear in preliminary form in . The results in this paper, and in a companion paper , extend upon and improve the results in . ∗Corresponding author. E-mail: firstname.lastname@example.org 1E-mail: email@example.com. This work was done while the author was at the Department of Computer Science & Engineering at the University of Minnesota. Research supported in part by a Grant-in-Aid of Research from the Graduate School of the University of Minnesota and by NSF grant CCR-9712226. 2 E-mail: firstname.lastname@example.org. Research supported in part by a Grant-in-Aid of Research from the Graduate School of the University of Minnesota and by NSF grant CCR-9712226. 3Part of this work was done while the author was at the Department of Computer Science, King’s College, London, UK. 4E-mail: email@example.com. Part of this work was done while the author was at the Max-Planck-Institut für Informatik, Saarbrücken, Germany, and at the Department of Computer Science & Engineering at the University of Minnesota.
© Springer-Verlag Berlin Heidelberg 1997.