{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:11Z","timestamp":1750309571223,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T00:00:00Z","timestamp":1741305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["IIS-18-14493 and CCF-20-07556"],"award-info":[{"award-number":["IIS-18-14493 and CCF-20-07556"]}]},{"name":"NSF","award":["CCF-15-40656 and CCF-20-08551"],"award-info":[{"award-number":["CCF-15-40656 and CCF-20-08551"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1736\/19 and 2261\/23"],"award-info":[{"award-number":["1736\/19 and 2261\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF\/US-Israel-BSF","award":["2019754"],"award-info":[{"award-number":["2019754"]}]},{"name":"Israel Ministry of Science and Technology","award":["103129"],"award-info":[{"award-number":["103129"]}]},{"name":"Blavatnik Computer Science Research"},{"name":"Shlomo Shmeltzer Institute for Smart Transportation"},{"DOI":"10.13039\/100022770","name":"Israeli Smart Transportation Research Center","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100022770","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"\n Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the\n assembly partitioning<\/jats:italic>\n sub-problem: Given a set\n \n \\(A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of parts, find a subset\n \n \\(S\\subset A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , referred to as a subassembly, such that\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n can be rigidly translated to infinity along a prescribed direction without colliding with\n \n \\(A\\setminus S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called\n connected-assembly-partitioning<\/jats:italic>\n , which additionally requires each of the two subassemblies,\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(A\\setminus S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , to be connected. We obtain the following results.\n \n \n \u2014<\/jats:label>\n \n We show that this problem is NP-complete, settling an open question posed by Wilson et al. 30 years ago, even when\n \n \\(A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n consists of unit-grid squares (i.e.,\n \n \\(A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is polyomino-shaped). For assemblies composed of polygons, we also show that deciding whether complete (dis)assembly is possible by repeatedly applying connected-assembly-partitioning, is NP-complete. Toward these results, we prove the NP-hardness of a new\n Planar 3-SAT<\/jats:sc>\n variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n On the positive side, we give an\n \n \\(O(2^{k}n^{2})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -time fixed-parameter tractable algorithm (requiring low degree polynomial-time preprocessing) for an assembly\n \n \\(A\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n consisting of polygons in the plane, where\n \n \\(n=|A|\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(k=|S|\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in\n \n \\(O(n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -time.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1145\/3711823","type":"journal-article","created":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T13:41:49Z","timestamp":1736516509000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Two-Handed Planar Assembly Partitioning with Connectivity Constraints"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9439-181X","authenticated-orcid":false,"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Department of Computer Science, Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, New York University Tandon School of Engineering, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3015-7514","authenticated-orcid":false,"given":"Tzvika","family":"Geft","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3345-3765","authenticated-orcid":false,"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,3,7]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.105"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/73833.73870"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1177\/0954406215584633"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.160"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0483-9"},{"key":"e_1_3_2_7_2","unstructured":"Alain Bourjault. 1984. Contribution \u00e0 une approche m\u00e9thodologique de l\u2019assemblage automatis\u00e9: \u00e9laboration automatique des s\u00e9quences op\u00e9ratoires. These D\u2019etat Universit\u00e9 de Franche-Comt\u00e9."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907009"},{"key":"e_1_3_2_9_2","series-title":"LIPIcs","first-page":"34:1","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"229","author":"Caballero David","year":"2022","unstructured":"David Caballero, Timothy Gomez, Robert T. Schweller, and Tim Wylie. 2022. Unique assembly verification in two-handed self-assembly. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, Vol. 229. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 34:1\u201334:21."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/120885.120892"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912500045"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/70.75905"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1177\/0954408918764459"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/COASE.2019.8843109"},{"key":"e_1_3_2_16_2","volume-title":"Complexity Measures for Assembly Sequences","author":"Goldwasser Michael","year":"1997","unstructured":"Michael Goldwasser. 1997. Complexity Measures for Assembly Sequences. Ph.D. Dissertation. Stanford University."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.506981"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2018.2791665"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910025"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1163\/156855397X00281"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10845-011-0578-5"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.506921"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00083-O"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90085-N"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0405033"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"issue":"4","key":"e_1_3_2_28_2","first-page":"2040","article-title":"Parallel self-assembly of polyominoes under uniform control inputs","volume":"2","author":"Manzoor Sheryl","year":"2017","unstructured":"Sheryl Manzoor, Samuel Sheckman, Jarrett Lonsford, Hoyeon Kim, Min Jun Kim, and Aaron T. Becker. 2017. Parallel self-assembly of polyominoes under uniform control inputs. IEEE Robotics and Automation Letters 2, 4 (2017), 2040\u20132047.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procir.2022.02.169"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73424"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187902"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2853758"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISATP.2003.1217194"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1177\/027836499501400403"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90048-5"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1991.131649"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2012.2188901"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711823","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3711823","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:15Z","timestamp":1750295955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3711823"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,7]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3711823"],"URL":"https:\/\/doi.org\/10.1145\/3711823","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,3,7]]},"assertion":[{"value":"2024-01-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}