Geometric Algorithms for Layered Manufacturing, with Applications

计算机辅助设计和制造（CAD/CAM）的进步现在使得使用“3D打印机”直接从数字表示中创建复杂三维物体的物理原型成为可能。其基础是一种称为分层制造（LM）的过程，该过程将数字模型切成几层，并依次打印这些层，每层都在前一层的上面。计算机辅助组织工程（Computer-Aided Tissue Engineering， CATE）是LM的一个新兴应用，其目标是通过创造人造器官来恢复和改善人类健康。在CATE中，LM用于构建可生物降解的支架结构，并将其植入细胞，然后生长形成所需的器官。本研究将解决LM中的几大类算法问题，包括几何优化、路径规划、分解和打包，并增加了利用解决方案来满足CATE中脚手架构建需求的目标。这项研究还将涉及一个实验部分，包括算法的实施和测试，以及通过物理原型验证结果。这项研究的智力价值在于，它将提供一个严格的算法框架，在这个框架内，可以解决LM中的许多具有挑战性的问题，包括脚手架的构建，从而导致重大的设计和性能改进。同时，这些应用将提供有趣的新问题，刺激几何算法的进一步研究。这项研究的更广泛的影响是，它将促进计算机科学与CAD/CAM和CATE之间的进一步互动，通过这些领域的本科生和研究生参与研究，将新主题整合到算法设计课程中，以及与工业界的合作。

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.