{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:41:51Z","timestamp":1750308111533,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>Layered manufacturing is a technology that allows physical prototypes of three-dimensional(3D) models to be built directly from their digital representation, as a stack of two-dimensional(2D) 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 estimating the minimum contact area. Also given is a technique for evaluating the quality of the estimate provided by any heuristic, which does not require knowledge of the (unknown and hard-to-compute) optimal solution; instead, it provides an indirect upper bound on the quality of the estimate 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.<\/jats:p>","DOI":"10.1145\/1187436.1210589","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":0,"title":["Heuristics for estimating contact area of supports in layered manufacturing"],"prefix":"10.1145","volume":"11","author":[{"given":"Ivayio","family":"Ilinkin","sequence":"first","affiliation":[{"name":"Rhodes College, Memphis, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Janardan","sequence":"additional","affiliation":[{"name":"University of Minnesota, Minneapolis, MN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Johnson","sequence":"additional","affiliation":[{"name":"University of Minnesota, Minneapolis, MN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Castillo","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Schwerdt","sequence":"additional","affiliation":[{"name":"Softwareb\u00fcro Bubel GmbH, Kirkel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. 528--537","author":"Agarwal P.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","first-page":"153","article-title":"Determination and evaluation of support structures in layered manufacturing","volume":"5","author":"Allen S.","year":"1995","journal-title":"Journal of Design and Manufacturing"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/PL00014421","article-title":"Feasibility of design in stereolithography","volume":"19","author":"Asberg B.","year":"1997","journal-title":"Algorithmica"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of AFIPS National Computer Conference.","volume":"44","author":"Baumgart B.","year":"1975"},{"key":"e_1_2_1_6_1","unstructured":"Computational Geometry Algorithms Library (CGAL). http:\/\/www.cgal.org.  Computational Geometry Algorithms Library (CGAL). http:\/\/www.cgal.org."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","DOI":"10.1142\/5064","volume-title":"Rapid Prototyping: Principles and Applications. World Scientific Publ","author":"Chua C.","year":"2003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry: Algorithms and Applications","author":"de Berg M.","year":"1997"},{"key":"e_1_2_1_9_1","unstructured":"DecimatorTM 1.0 Raindrop Geomagic Inc. North Carolina. http:\/\/www.geomagic.com\/products\/decimate\/.  DecimatorTM 1.0 Raindrop Geomagic Inc. North Carolina. http:\/\/www.geomagic.com\/products\/decimate\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90038-X"},{"volume-title":"Fundamentals of StereoLithography","author":"Jacobs P.","key":"e_1_2_1_11_1"},{"volume-title":"Dept. of CS & E, Univ. of Minnesota","author":"Johnson E.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00003-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00002-4"},{"volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","year":"1999","author":"Mehlhorn K.","key":"e_1_2_1_16_1"},{"volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","year":"1993","author":"Mulmuley K.","key":"e_1_2_1_17_1"},{"volume-title":"Proceedings of the 5th ACM Symposium on Solid Modeling and Applications. 285--295","author":"McMains S.","key":"e_1_2_1_18_1"},{"volume-title":"Computational Geometry: An Introduction","year":"1993","author":"Preparata F.","key":"e_1_2_1_19_1"},{"volume-title":"Proc. 18th ACM Symposium on Computational Geometry. 283--292","author":"Shaul H.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","unstructured":"VRMeshTM VirtualGrid Inc. Washington. http:\/\/www.vrmesh.com.  VRMeshTM VirtualGrid Inc. Washington. http:\/\/www.vrmesh.com."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1210589","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1210589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1210589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":19,"alternative-id":["10.1145\/1187436.1210589"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1210589","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}