{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T10:25:49Z","timestamp":1791282349940,"version":"4.1.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,11,19]],"date-time":"2014-11-19T00:00:00Z","timestamp":1416355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["611370"],"award-info":[{"award-number":["611370"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Israeli Ministry of Science"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2014,11,19]]},"abstract":"<jats:p>\n                    A shape is pyramidal if it has a flat base with the remaining boundary forming a height function over the base. Pyramidal shapes are optimal for molding, casting, and layered 3D printing. However, many common objects are not pyramidal. We introduce an algorithm for\n                    <jats:italic>approximate pyramidal shape decomposition<\/jats:italic>\n                    . The general exact pyramidal decomposition problem is NP-hard. We turn this problem into an NP-complete problem which admits a practical solution. Specifically, we link pyramidal decomposition to the\n                    <jats:italic>Exact Cover Problem<\/jats:italic>\n                    (ECP). Given an input shape\n                    <jats:italic>S<\/jats:italic>\n                    , we develop clustering schemes to derive a set of building blocks for approximate pyramidal parts of\n                    <jats:italic>S<\/jats:italic>\n                    . The building blocks are then combined to yield a set of candidate pyramidal parts. Finally, we employ Knuth's Algorithm X over the candidate parts to obtain solutions to ECP as pyramidal shape decompositions. Our solution is equally applicable to 2D or 3D shapes, and to shapes with polygonal or smooth boundaries, with or without holes. We demonstrate our algorithm on numerous shapes and evaluate its performance.\n                  <\/jats:p>","DOI":"10.1145\/2661229.2661244","type":"journal-article","created":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T09:21:03Z","timestamp":1416302463000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":83,"title":["Approximate pyramidal shape decomposition"],"prefix":"10.1145","volume":"33","author":[{"given":"Ruizhen","family":"Hu","sequence":"first","affiliation":[{"name":"Simon Fraser University and Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Honghua","family":"Li","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Cohen-Or","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.120"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12169"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366149"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.439"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213031"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218654303000139"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000687"},{"key":"e_1_2_1_10_1","unstructured":"Heckbert P. S. and Garland M. 1997. Survey of polygonal surface simplication algorithms. In SIGGRAPH Course on Multiresolution Surface Modeling.  Heckbert P. S. and Garland M. 1997. Survey of polygonal surface simplication algorithms. In SIGGRAPH Course on Multiresolution Surface Modeling ."},{"key":"e_1_2_1_11_1","unstructured":"Knuth D. 2000. Dancing links. Millenial Perspectives in Computer Science 159--187.  Knuth D. 2000. Dancing links. Millenial Perspectives in Computer Science 159--187."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2009.2021324"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236246.1236265"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90097-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366148"},{"key":"e_1_2_1_16_1","article-title":"Finding undercut-free parting directions for polygons with curved edges","author":"McMains S.","year":"2005","unstructured":"McMains , S. , and Chen , X. 2005 . Finding undercut-free parting directions for polygons with curved edges . Journal of Computing and Information Science in Engineering 6. McMains, S., and Chen, X. 2005. Finding undercut-free parting directions for polygons with curved edges. Journal of Computing and Information Science in Engineering 6.","journal-title":"Journal of Computing and Information Science in Engineering 6."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01178.x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383301"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461957"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(03)00107-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90020-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01103.x"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Sharvit D. Chan J. Tek H. and Kimia B. B. 1998. Symmetry-based indexing of image databases. J. Visual Communication and image representation 9 366--380.  Sharvit D. Chan J. Tek H. and Kimia B. B. 1998. Symmetry-based indexing of image databases. J. Visual Communication and image representation 9 366--380.","DOI":"10.1006\/jvci.1998.0396"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185544"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/357346.357348"},{"key":"e_1_2_1_27_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer . Vazirani, V. V. 2001. Approximation Algorithms. Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508382"},{"key":"e_1_2_1_29_1","first-page":"1601","article-title":"Self-tuning spectral clustering","volume":"17","author":"Zelnik-Manor L.","year":"2004","unstructured":"Zelnik-Manor , L. , and Perona , P. 2004 . Self-tuning spectral clustering . In Proc. Advances in Neural Information Processing Systems (NIPS) , vol. 17 , 1601 -- 1608 . Zelnik-Manor, L., and Perona, P. 2004. Self-tuning spectral clustering. In Proc. Advances in Neural Information Processing Systems (NIPS), vol. 17, 1601--1608.","journal-title":"Proc. Advances in Neural Information Processing Systems (NIPS)"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661229.2661244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2661229.2661244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:05Z","timestamp":1750212785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661229.2661244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,19]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,11,19]]}},"alternative-id":["10.1145\/2661229.2661244"],"URL":"https:\/\/doi.org\/10.1145\/2661229.2661244","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,19]]},"assertion":[{"value":"2014-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}