Efficient Algorithms for Geometric Problems in Computer-Aided Manufacturing

Computer-aided manufacturing (CAM) is an area of manufacturing where computer algorithms are used for planning and controlling fabrication processes of three dimensional objects. Most often the final surface is created by folding or sculpting the raw material. In this dissertation we study several problems arising in CAM. Specifically, we develop a memory-efficient technique for constructing a triangular mesh of a surface given its continuous representation and prove that the problem of flattening an already triangulated surface is NP-hard. We also develop algorithms for two problems related to finding an optimal surface orientation with respect to the machining tool: we show how to efficiently partition a surface into two sub-patches, subject to certain objective functions, and we show how to find an orientation of the surface that maximizes the area that can be sculpted during a single setup. Furthermore, we present methods for finding a feasible set of tool orientations for already computed sculpting paths. Since problems in CAM are often geometric in nature, as a result of our work, we develop several algorithmic techniques and data structures that are interesting from the point of view of theoretical computational geometry, geometric optimization, and graph theory. For example, we reduce the space requirement for a class of problems that seek a path from among many shortest paths in certain weighted grid graphs, we develop new algorithms for processing an off-line sequence of insertions and deletions of convex polygons interspersed with certain point queries on the common intersection of the polygons, and for finding a line segment of a fixed-length that intersects the maximum number of given polygons. We also study two problems on interval structures that arise in CAM. We give efficient algorithms for a single-source K-link shortest path problem on an interval graph and for an optimal color covering problem for n points on a line, where each point is assigned one of m colors. Some of our results improve existing algorithms, others are new. Our methods combine geometric modeling, new algorithmic techniques, and new data structures. Many of our algorithms find applications in areas outside of computer-aided manufacturing.