On some geometric optimization problems in layered manufacturing

Jayanth Majhi, Ravi Janardan, Michiel Smid, Prosenjit Gupta

Research output: Contribution to journalArticlepeer-review

72 Scopus citations

Abstract

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 stair-step error on the surfaces of the manufactured object under various formulations, 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 only to convex polyhedra. The techniques used to obtain these results include construction and searching of certain arrangements on the sphere, 3D convex hulls, halfplane range searching, and constrained optimization.

Original languageEnglish (US)
Pages (from-to)219-239
Number of pages21
JournalComputational Geometry: Theory and Applications
Volume12
Issue number3-4
DOIs
StatePublished - Apr 1999

Bibliographical note

Funding Information:
I Portions of this work appear in preliminary form in [17]. The results in this paper, and in a companion paper [18], extend upon and improve the results in [17]. ∗Corresponding author. E-mail: michiel@isg.cs.uni-magdeburg.de 1E-mail: jayanth_majhi@mentorg.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: janardan@cs.umn.edu. 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: pgupta@delsoft.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.

Keywords

  • Computational geometry
  • Layered manufacturing
  • Optimization

Fingerprint Dive into the research topics of 'On some geometric optimization problems in layered manufacturing'. Together they form a unique fingerprint.

Cite this