2017/08/01 by Prosenjit Bose, Tzvika Geft, Dan Halperin +2 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Manufacturing and Logistics Optimization #Algorithm #Artificial intelligence #Casting #Combinatorics #Composite material #Computational Geometry and Mesh Generation #Computer science #Engineering #Engineering drawing #Geometry #Manufacturing Process and Optimization #Materials science #Mathematics #Mold #Object (grammar) #Optimization and Packing Problems #Orientation (vector space) #Polyhedron #Process (computing) #Product (mathematics) #cs.CG
paper · pdf · doi:10.1109/coase.2017.8256076
13 pages. This version includes a proof that establishes the optimality of our algorithms, which extends our CASE2017 version. Submitted to Computer-Aided Design
openalex publication_date 2017/08/14 · openalex created_date 2019/07/30 · arxiv created 2021/06/07 · arxiv updated 2021/06/08 · openalex updated_date 2026/08/05
Casting is a manufacturing process where liquid material is poured into a mold having the shape of a desired product. After the material solidifies, the product is removed from the mold. We study the case where the mold is made of a single part and the object to be produced is a three-dimensional polyhedron. Objects that can be produced this way are called castable with a single-part mold. A direction in which the object can be removed without breaking the mold is called a valid removal direction. We give an O(n)-time algorithm that decides whether a given polyhedron with n facets is castable with a single-part mold. When possible, our algorithm provides an orientation of the polyhedron in the mold and a direction in which the product can be removed without breaking the mold. Moreover, we provide an optimal Θ(n log n)-time algorithm to compute all valid removal directions for polyhdera that are castable with a single-part mold. Both algorithms are an improvement by a linear factor over the previously best known algorithms for both of these problems.