{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:32Z","timestamp":1750306772281,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["NSC-98-2221-E-155-053, and NSC-101-2221-E-155-075"],"award-info":[{"award-number":["NSC-98-2221-E-155-053, and NSC-101-2221-E-155-075"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>In order to use rectangular corner stitching data structures in storing parameterized orthogonal layouts, parameterized polygons in the layouts must be partitioned into rectangles. Likewise, in order to use trapezoidal corner stitching data structures in storing parameterized 45-degree layouts, parameterized polygons in the layouts have to be partitioned into trapezoids. In this article, a parallel polygon partitioning algorithm is proposed; the algorithm is capable of partitioning parameterized orthogonal polygons into parameterized rectangles as well as partitioning parameterized 45-degree polygons into parameterized trapezoids. Additionally, the algorithm can be used to partition fixed-coordinate polygons. By adopting the dual-scanline technique, which involves using two scanlines to concurrently sweep an input polygon, the parallel partitioning algorithm can process vertices and edges of the input polygon efficiently. The parallel polygon partitioning algorithm has been implemented in C++ with the use of OpenMP. Compared with a sequential partitioning program which uses a single scanline, our parallel partitioning program can achieve 20% to 30% speedup while partitioning large parameterized polygons or partitioning parameterized polygons with complex constraints.<\/jats:p>","DOI":"10.1145\/2505015","type":"journal-article","created":{"date-parts":[[2013,11,6]],"date-time":"2013-11-06T14:09:19Z","timestamp":1383746959000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygons"],"prefix":"10.1145","volume":"18","author":[{"given":"Yao-Lin","family":"Chang","sequence":"first","affiliation":[{"name":"Yuan Ze University, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I-Lun","family":"Tseng","sequence":"additional","affiliation":[{"name":"Yuan Ze University, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,10,25]]},"reference":[{"volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe. 414--420","author":"Adler T.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","unstructured":"Arai K. and Kikuchi H. 2005. Basic cell of gate array semiconductor device gate array semiconductor device and layout method for gate array semiconductor device. United States Patent No. US 6842886 B2.  Arai K. and Kikuchi H. 2005. Basic cell of gate array semiconductor device gate array semiconductor device and layout method for gate array semiconductor device. United States Patent No. US 6842886 B2."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Baker R. J. 2010. CMOS Circuit Design Layout and Simulation Wiley-IEEE Press.   Baker R. J. 2010. CMOS Circuit Design Layout and Simulation Wiley-IEEE Press.","DOI":"10.1002\/9780470891179"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TADVP.2006.890227"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"volume-title":"Proceedings of IEEE Custom Integrated Circuits Conference. 717--720","author":"Blaschke V.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923417"},{"key":"e_1_2_1_9_1","unstructured":"Chapman B. Jost G. and van der Pas R. 2007. Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press.   Chapman B. Jost G. and van der Pas R. 2007. Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press."},{"key":"e_1_2_1_10_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2009. Introduction to Algorithms Third Edition. MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2009. Introduction to Algorithms Third Edition. MIT Press."},{"volume-title":"Proceedings of the IEEE Region 10 Conference. 750--753","author":"Feng W. S.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10549"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1983.262975"},{"volume-title":"Proceedings of the Design Automation Conference. 173--179","author":"Hamachi G. T.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the IEEE Southwest Symposium on Mixed-Signal Design. 233--236","author":"Kumar S.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/330855.331038"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.45858"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653827"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Mohan S. S. Hershenson M. D. M. Boyd S. P. and Lee T. H. 1999. Simple accurate expressions for planar spiral inductances. IEEE J. Solid-State Circuits. 1419--1424.  Mohan S. S. Hershenson M. D. M. Boyd S. P. and Lee T. H. 1999. Simple accurate expressions for planar spiral inductances. IEEE J. Solid-State Circuits. 1419--1424.","DOI":"10.1109\/4.792620"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.3182"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.52171"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(85)90159-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228458"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1984.1270061"},{"volume-title":"Proceedings of the Design Automation Conference. 152--159","author":"Ousterhout J. K.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the Design Automation Conference. 166--172","author":"Scott W. S.","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the Design Automation Conference. 286--292","author":"Scott W. S.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016568.1016637"},{"volume-title":"Proceedings of the Design Automation Conference. 160--165","author":"Taylor G. S.","key":"e_1_2_1_29_1"},{"volume-title":"Proceedings of the IEEE Region 10 Conference. 1531--1534","author":"Tseng I.-L.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127908.1127992"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367045.1367061"},{"volume-title":"Proceedings of the IEEE International Symposium on Next-Generation Electronics. 333--336","author":"Wang Z.-W.","key":"e_1_2_1_33_1"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2505015","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2505015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:57Z","timestamp":1750231737000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2505015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2505015"],"URL":"https:\/\/doi.org\/10.1145\/2505015","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2012-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}