{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:40Z","timestamp":1750220560747,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            The\n            <jats:italic>cavity decomposition problem<\/jats:italic>\n            is a computational geometry problem, arising in the context of modern electronic CAD systems, that concerns detecting the generation and propagation of electromagnetic noise into multi-layer printed circuit boards. Algorithmically speaking, the problem can be formulated so as to contain, as sub-problems, the well-known\n            <jats:italic>polygon schematization<\/jats:italic>\n            and\n            <jats:italic>polygon decomposition<\/jats:italic>\n            problems. Given a polygon\n            <jats:italic>P<\/jats:italic>\n            and a finite set\n            <jats:italic>C<\/jats:italic>\n            of given directions, polygon schematization asks for computing a\n            <jats:italic>C<\/jats:italic>\n            -oriented polygon\n            <jats:italic>P<\/jats:italic>\n            \u2032 with \u201clow complexity\u201d and \u201chigh resemblance\u201d to\n            <jats:italic>P<\/jats:italic>\n            , whereas polygon decomposition asks for partitioning\n            <jats:italic>P<\/jats:italic>\n            into a set of basic polygonal elements (e.g., triangles) whose size is as small as possible.\n          <\/jats:p>\n          <jats:p>In this article, we present three different solutions for the cavity decomposition problem, which are obtained by suitably combining existing algorithms for polygon schematization and decomposition, by considering different input parameters, and by addressing both methodological and implementation issues. Since it is difficult to compare the three solutions on a theoretical basis, we present an extensive experimental study, employing both real-world and random data, conducted to assess their performance. We rank the proposed solutions according to the results of the experimental evaluation, and provide insights on natural candidates to be adopted, in practice, as modules of modern printed circuit board design software tools, depending on the observed performance and on the different constraints on the desired output.<\/jats:p>","DOI":"10.1145\/3462760","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T23:54:22Z","timestamp":1629158062000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Combining Polygon Schematization and Decomposition Approaches for Solving the Cavity Decomposition Problem"],"prefix":"10.1145","volume":"7","author":[{"given":"Serafino","family":"Cicerone","sequence":"first","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}]},{"given":"Mattia","family":"D\u2019emidio","sequence":"additional","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}]},{"given":"Daniele","family":"Frigioni","sequence":"additional","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}]},{"given":"Filippo Tirabassi","family":"Pascucci","sequence":"additional","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}]}],"member":"320","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Agarwal and Micha Sharir","author":"Pankaj","year":"2000","unstructured":"Pankaj K. Agarwal and Micha Sharir . 2000 . Arrangements and their applications. In Handbook of Computational Geometry. Elsevier , 49\u2013119. Pankaj K. Agarwal and Micha Sharir. 2000. Arrangements and their applications. In Handbook of Computational Geometry. Elsevier, 49\u2013119."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897826.2927362"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Bouts Quirijn W.","year":"2016","unstructured":"Quirijn W. Bouts , Irina Kostitsyna , Marc J. van Kreveld , Wouter Meulemans , Willem Sonke , and Kevin Verbeek . 2016 . Mapping polygons to the grid with small Hausdorff and Fr\u00e9chet distance . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . Article 22, 16 pages. Quirijn W. Bouts, Irina Kostitsyna, Marc J. van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek. 2016. Mapping polygons to the grid with small Hausdorff and Fr\u00e9chet distance. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). Article 22, 16 pages."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818373"},{"volume-title":"Handbook of Combinatorial Optimization","author":"Cheng Xiuzhen","key":"e_1_2_1_5_1","unstructured":"Xiuzhen Cheng , Ding-Zhu Du , Joon-Mo Kim , and Lu Ruan . 2005. Optimal rectangular partitions . In Handbook of Combinatorial Optimization . Springer , 313\u2013327. Xiuzhen Cheng, Ding-Zhu Du, Joon-Mo Kim, and Lu Ruan. 2005. Optimal rectangular partitions. In Handbook of Combinatorial Optimization. Springer, 313\u2013327."},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Computational Science and Its Applications","author":"Cicerone Serafino","unstructured":"Serafino Cicerone and Matteo Cermignani . 2012. Fast and simple approach for polygon schematization . In Computational Science and Its Applications . Lecture Notes in Computer Science , Vol. 7333 . Springer , 267\u2013279. Serafino Cicerone and Matteo Cermignani. 2012. Fast and simple approach for polygon schematization. In Computational Science and Its Applications. Lecture Notes in Computer Science, Vol. 7333. Springer, 267\u2013279."},{"key":"e_1_2_1_7_1","series-title":"Lecture Notes in Computer Science","volume-title":"Discrete and Computational Geometry and Graphs","author":"Cicerone Serafino","unstructured":"Serafino Cicerone and Gabriele Di Stefano . 2014. Decomposing octilinear polygons into triangles and rectangles . In Discrete and Computational Geometry and Graphs . Lecture Notes in Computer Science , Vol. 8845 . Springer , 18\u201330. Serafino Cicerone and Gabriele Di Stefano. 2014. Decomposing octilinear polygons into triangles and rectangles. In Discrete and Computational Geometry and Graphs. Lecture Notes in Computer Science, Vol. 8845. Springer, 18\u201330."},{"volume-title":"Proceedings of the 20th International Zurich Symposium on Electromagnetic Compatibility (EMC-Zurich\u201909)","author":"Cicerone Serafino","key":"e_1_2_1_8_1","unstructured":"Serafino Cicerone , Antonio Orlandi , Bruce Archambeault , Samuel Connor , Jun Fan , and James L. Drewniak . 2009. Cavities\u2019 identification algorithm for power integrity analysis of complex boards . In Proceedings of the 20th International Zurich Symposium on Electromagnetic Compatibility (EMC-Zurich\u201909) . IEEE, Los Alamitos, CA, 253\u2013256. Serafino Cicerone, Antonio Orlandi, Bruce Archambeault, Samuel Connor, Jun Fan, and James L. Drewniak. 2009. Cavities\u2019 identification algorithm for power integrity analysis of complex boards. In Proceedings of the 20th International Zurich Symposium on Electromagnetic Compatibility (EMC-Zurich\u201909). IEEE, Los Alamitos, CA, 253\u2013256."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.01.037"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_27"},{"key":"e_1_2_1_11_1","first-page":"112","article-title":"Algorithms for the reduction of the number of points required to represent a digitized line or its caricature","volume":"10","author":"Douglas David H.","year":"1973","unstructured":"David H. Douglas and Thomas K. Peucker . 1973 . Algorithms for the reduction of the number of points required to represent a digitized line or its caricature . Canadian Geographer 10 , 2 (1973), 112 \u2013 122 . David H. Douglas and Thomas K. Peucker. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Canadian Geographer 10, 2 (1973), 112\u2013122.","journal-title":"Canadian Geographer"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840380"},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Computing and Combinatorics","author":"Durocher Stephane","unstructured":"Stephane Durocher and Saeed Mehrabi . 2012. Computing partitions of rectilinear polygons with minimum stabbing number . In Computing and Combinatorics . Lecture Notes in Computer Science , Vol. 7434 . Springer , 228\u2013239. Stephane Durocher and Saeed Mehrabi. 2012. Computing partitions of rectilinear polygons with minimum stabbing number. In Computing and Combinatorics. Lecture Notes in Computer Science, Vol. 7434. Springer, 228\u2013239."},{"volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Eppstein David","key":"e_1_2_1_14_1","unstructured":"David Eppstein . 2010. Graph-theoretic solutions to computational geometry problems . In Graph-Theoretic Concepts in Computer Science . Springer , 1\u201316. David Eppstein. 2010. Graph-theoretic solutions to computational geometry problems. In Graph-Theoretic Concepts in Computer Science. Springer, 1\u201316."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(84)90139-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215033"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(86)80027-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50012-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90011-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/22.763156"},{"volume-title":"Proceedings of the 5th Annual Symposium on Computational Geometry (SCG\u201989)","author":"Liou W. T.","key":"e_1_2_1_22_1","unstructured":"W. T. Liou , J. J. Tan , and R. C. Lee . 1989. Minimum partitioning simple rectilinear polygons in -time . In Proceedings of the 5th Annual Symposium on Computational Geometry (SCG\u201989) . ACM, New York, NY, 344\u2013353. W. T. Liou, J. J. Tan, and R. C. Lee. 1989. Minimum partitioning simple rectilinear polygons in -time. In Proceedings of the 5th Annual Symposium on Computational Geometry (SCG\u201989). ACM, New York, NY, 344\u2013353."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130308"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90105-4"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG\u201917)","author":"L\u00f6ffler Maarten","year":"2017","unstructured":"Maarten L\u00f6ffler and Wouter Meulemans . 2017 . Discretized approaches to schematization . In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG\u201917) . 1\u20136. Maarten L\u00f6ffler and Wouter Meulemans. 2017. Discretized approaches to schematization. In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG\u201917). 1\u20136."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aeue.2015.02.012"},{"volume-title":"A Guide to Experimental Algorithmics","author":"McGeoch Catherine C.","key":"e_1_2_1_27_1","unstructured":"Catherine C. McGeoch . 2012. A Guide to Experimental Algorithmics . Cambridge University Press . Catherine C. McGeoch. 2012. A Guide to Experimental Algorithmics. Cambridge University Press."},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","volume-title":"Graph Drawing","author":"Merrick Damian","unstructured":"Damian Merrick and Joachim Gudmundsson . 2006. Path simplification for metro map layout . In Graph Drawing . Lecture Notes in Computer Science , Vol. 4372 . Springer , 258\u2013269. Damian Merrick and Joachim Gudmundsson. 2006. Path simplification for metro map layout. In Graph Drawing. Lecture Notes in Computer Science, Vol. 4372. Springer, 258\u2013269."},{"key":"e_1_2_1_29_1","unstructured":"Wouter Meulemans. 2016. Discretized approaches to schematization. arXiv:1606.06488. http:\/\/arxiv.org\/abs\/1606.06488.  Wouter Meulemans. 2016. Discretized approaches to schematization. arXiv:1606.06488. http:\/\/arxiv.org\/abs\/1606.06488."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/6040.861546"},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Data Structures","author":"Neyer Gabriele","unstructured":"Gabriele Neyer . 1999. Line simplification with restricted orientations . In Algorithms and Data Structures . Lecture Notes in Computer Science , Vol. 1663 . Springer , 13\u201324. Gabriele Neyer. 1999. Line simplification with restricted orientations. In Algorithms and Data Structures. Lecture Notes in Computer Science, Vol. 1663. Springer, 13\u201324."},{"volume-title":"Towards data-driven multilinear metro maps","author":"Nickel Soeren","key":"e_1_2_1_32_1","unstructured":"Soeren Nickel and Martin N\u00f6llenburg . 2020. Towards data-driven multilinear metro maps . In Diagrammatic Representation and Inference, Ahti-Veikko Pietarinen, Peter Chapman, Leonie Bosveld-de Smet, Valeria Giardino, James Corter, and Sven Linker (Eds.). Springer International , Cham, Switzerland , 153\u2013161. Soeren Nickel and Martin N\u00f6llenburg. 2020. Towards data-driven multilinear metro maps. In Diagrammatic Representation and Inference, Ahti-Veikko Pietarinen, Peter Chapman, Leonie Bosveld-de Smet, Valeria Giardino, James Corter, and Sven Linker (Eds.). Springer International, Cham, Switzerland, 153\u2013161."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.81"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems.","author":"Ohtsuki Tatsuo","year":"1982","unstructured":"Tatsuo Ohtsuki . 1982 . Minimum dissection of rectilinear regions . In Proceedings of the IEEE International Symposium on Circuits and Systems. Tatsuo Ohtsuki. 1982. Minimum dissection of rectilinear regions. In Proceedings of the IEEE International Symposium on Circuits and Systems."},{"volume-title":"Planar Circuits for Microwaves and Lightwaves","author":"Okoshi T.","key":"e_1_2_1_35_1","unstructured":"T. Okoshi . 1985. Planar Circuits for Microwaves and Lightwaves . Springer-Verlag . https:\/\/doi.org\/10.1007\/978-3-642-70083-5 10.1007\/978-3-642-70083-5 T. Okoshi. 1985. Planar Circuits for Microwaves and Lightwaves. Springer-Verlag. https:\/\/doi.org\/10.1007\/978-3-642-70083-5"},{"key":"e_1_2_1_36_1","unstructured":"Jeremy G. Siek Lie-Quan Lee and Andrew Lumsdaine. 2002. The Boost Graph Library: User Guide and Reference Manual. Pearson\/Prentice Hall.  Jeremy G. Siek Lie-Quan Lee and Andrew Lumsdaine. 2002. The Boost Graph Library: User Guide and Reference Manual. Pearson\/Prentice Hall."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2012.05.012"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TADVP.2004.831897"},{"key":"e_1_2_1_39_1","series-title":"Lecture Notes in Computer Science","volume-title":"Web and Wireless Geographical Information Systems","author":"Swan Jerry","unstructured":"Jerry Swan , Suchith Anand , J. Mark Ware , and Mike Jackson . 2007. Automated schematization for web service applications . In Web and Wireless Geographical Information Systems . Lecture Notes in Computer Science , Vol. 4857 . Springer , 216\u2013226. Jerry Swan, Suchith Anand, J. Mark Ware, and Mike Jackson. 2007. Automated schematization for web service applications. In Web and Wireless Geographical Information Systems. Lecture Notes in Computer Science, Vol. 4857. Springer, 216\u2013226."},{"key":"e_1_2_1_40_1","volume-title":"Area preserving cartographic line generalization. Kartografija i Geoinformacije 8 (June","author":"Tuti\u0107 Dra\u017een","year":"2009","unstructured":"Dra\u017een Tuti\u0107 . 2009. Area preserving cartographic line generalization. Kartografija i Geoinformacije 8 (June 2009 ), 85\u2013100. Dra\u017een Tuti\u0107. 2009. Area preserving cartographic line generalization. Kartografija i Geoinformacije 8 (June 2009), 85\u2013100."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1179\/caj.1993.30.1.46"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3462760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:31Z","timestamp":1750195711000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3462760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3462760"],"URL":"https:\/\/doi.org\/10.1145\/3462760","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}