Geometric Algorithms for Layered Manufacturing, with Applications

Advances in computer-aided design and manufacturing (CAD/CAM) now make it possible to create physical prototypes of complex three-dimensional objects directly from their digital representations, using a '3D printer'. The basis for this is a process called Layered Manufacturing (LM), which slices the digital model into layers and prints these layers successively, each atop the previous one. An emerging application of LM is Computer-Aided Tissue Engineering (CATE), whose goal is to restore and improve human health through the creation of artificial organs. LM is used in CATE to construct biodegradable scaffold structures and to seed them with cells that then grow to form the desired organs.

This research will address several broad classes of algorithmic problems in LM, including geometric optimization, path planning, decomposition, and packing, with the added goal of leveraging the solutions to meet the needs of scaffold construction in CATE. The research will also involve an experimental component, which includes implementation and testing of algorithms and verification of results via physical prototyping. The intellectual merit of the research is that it will provide a rigorous algorithmic framework within which a number of challenging problems in LM, including scaffold construction, can be addressed, thereby leading to significant design and performance improvements. Simultaneously, these applications will provide interesting new problems that will stimulate further research in geometric algorithms. The broader impacts of the research are that it will foster further interaction between computer science and CAD/CAM and CATE through the involvement of undergraduate and graduate students from these areas in the research, the integration of new topics into the algorithm design curriculum, and collaboration with industry.