Ilinkin, IvayloJanardan, RaviSmid, MichielJohnson, EricCastillo, PaulSchwerdt, Jörg2020-09-022020-09-022004-01-05https://hdl.handle.net/11299/215595Layered Manufacturing is a technology that allows physicalprototypes of three-dimensional models to be built directlyfrom their digital representation, as a stack of two-dimensional layers. A key design problem here is the choice of a suitable direction in which the digital model should be oriented and built so as to minimize the area of contact between the prototype and temporary support structures that are generated during the build. Devising an efficient algorithm for computing such a direction has remained a difficult problem for quite some time. In this paper, a suite of efficient and practical heuristics is presented for approximating the minimum contact-area. Also given is a technique for evaluating the quality of the approximation of any heuristic, which doesnot require knowledge of the (unknown and hard-to-compute) optimal solution; instead, it provides an indirect upper bound on the quality of the approximation via two relatively easy-to-compute quantities. The algorithms are based on various techniques from computational geometry, such as ray-shooting, convex hulls, boolean operations on polygons, and spherical arrangements, and have been implemented and tested. Experimental results on a wide range of real-world models show that the heuristics perform quite well in practice.en-USReport