On some geometric optimization problems in layered manufacturing

Jayanth Majhi, Ravi Janardan, Michiel Smid, Prosenjit Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 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 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 languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings
EditorsAndrew Rau-Chaplin, Frank Dehne, Jorg-Rudiger Sack, Roberto Tamassia
PublisherSpringer Verlag
Pages136-149
Number of pages14
ISBN (Print)3540633073, 9783540633075
StatePublished - Jan 1 1997
Event5th International Workshop on Algorithms and Data Structures, WADS 1997 - Halifax, Canada
Duration: Aug 6 1997Aug 8 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1272
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Workshop on Algorithms and Data Structures, WADS 1997
CountryCanada
CityHalifax
Period8/6/978/8/97

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

  • Cite this

    Majhi, J., Janardan, R., Smid, M., & Gupta, P. (1997). On some geometric optimization problems in layered manufacturing. In A. Rau-Chaplin, F. Dehne, J-R. Sack, & R. Tamassia (Eds.), Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings (pp. 136-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1272). Springer Verlag.