{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:15:54Z","timestamp":1770963354722,"version":"3.50.1"},"reference-count":18,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Polygon Boolean operations are widely used in integrated circuit (IC) layout processing tasks such as design rule checking (DRC) and optical proximity correction (OPC). Single-threaded Boolean algorithms cannot meet the efficiency demand of modern IC layouts, necessitating parallel algorithms for acceleration. However, existing parallel algorithms exhibit unsatisfactory parallel speedups and limited scalability, which typically stem from an inefficient merging phase that uses generic Boolean OR operations and redundantly reprocesses all edges of polygons on grid boundaries. To solve these problems, we proposed Polygon Tailor, a novel parallel algorithm for polygon Boolean operations that employs a data-parallel strategy and a new merging approach performing incremental XOR operations solely on edges along grid boundaries, eliminating redundant computations in previous methods. This innovation drastically reduces the grid-merging time by 1\u20132 orders of magnitude. Compared with the parallel implementation from a commercial layout processing tool, PolygonTailor is on average 5.08\u00d7 faster and up to 14.36\u00d7 faster for OR operations that generate highly complex polygons.<\/jats:p>","DOI":"10.3390\/a19020145","type":"journal-article","created":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T17:10:52Z","timestamp":1770743452000},"page":"145","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["PolygonTailor: A Parallel Algorithm for Polygon Boolean Operations in IC Layout Processing"],"prefix":"10.3390","volume":"19","author":[{"given":"Zhirui","family":"Niu","sequence":"first","affiliation":[{"name":"Institute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, China"},{"name":"School of Integrated Circuits, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4714-913X","authenticated-orcid":false,"given":"Ruian","family":"Ji","sequence":"additional","affiliation":[{"name":"Institute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, China"},{"name":"School of Integrated Circuits, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guan","family":"Wang","sequence":"additional","affiliation":[{"name":"HiSilicon, Shenzhen 518129, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siao","family":"Guo","sequence":"additional","affiliation":[{"name":"HiSilicon, Shenzhen 518129, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shijie","family":"Ye","sequence":"additional","affiliation":[{"name":"HiSilicon, Shenzhen 518129, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8121-657X","authenticated-orcid":false,"given":"Lan","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, China"},{"name":"School of Integrated Circuits, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2026,2,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Wang, Z., and Wang, C. (2024, January 22\u201325). E2E-Check: End to End GPU-Accelerated Design Rule Checking with Novel Mask Boolean Algorithms. Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC), Incheon, Republic of Korea.","DOI":"10.1109\/ASP-DAC58780.2024.10473843"},{"key":"ref_2","unstructured":"Pais, A.P.V., Anido, M.L., and Oliveira, C.E.T. (2001, January 14\u201317). Developing a distributed architecture for design rule checking. Proceedings of the 44th IEEE Midwest Symposium on Circuits and Systems (MWSCAS 2001), Dayton, OH, USA."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Luo, T.-C., Leong, E., Chao, M.C.-T., Fisher, P.A., and Chang, W.-H. (2010, January 2\u20134). Mask versus Schematic\u2014An enhanced design-verification flow for first silicon success. Proceedings of the 2010 IEEE International Test Conference, Austin, TX, USA.","DOI":"10.1109\/TEST.2010.5699238"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Spence, C., and Goad, S. (2009). Computational requirements for OPC. Proc. SPIE 7275, Design for Manufacturability through Design-Process Integration III, SPIE. 72750U.","DOI":"10.1117\/12.813522"},{"key":"ref_5","unstructured":"Singh, V.K. (2026, January 04). Accelerating Computational Lithography: Enabling our Electronic Future. Available online: https:\/\/www.nvidia.com\/en-us\/on-demand\/session\/gtcspring23-s52510\/."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1016\/j.cad.2010.06.008","article-title":"Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD","volume":"42","author":"Simonson","year":"2010","journal-title":"Comput. Aided Des."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/274363.274364","article-title":"Efficient clipping of arbitrary polygons","volume":"17","author":"Greiner","year":"1998","journal-title":"ACM Trans. Graph."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/129902.129906","article-title":"A generic solution to polygon clipping","volume":"35","author":"Vatti","year":"1992","journal-title":"Commun. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1016\/j.cageo.2008.08.009","article-title":"A new algorithm for computing Boolean operations on polygons","volume":"35","author":"Martinez","year":"2009","journal-title":"Comput. Geosci."},{"key":"ref_10","unstructured":"Zhang, P., Teng, X., Fan, J., Meng, X., Zhao, Q., and Kang, W. (2023). Comparison of 4 vector polygon clipping algorithms in the spatial overlay analysis of GIS using simple feature model. Proc. SPIE 12797, Second International Conference on Geographic Information and Remote Sensing Technology (GIRST 2023), SPIE. 127972D."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Puri, S., and Prasad, S.K. (2015, January 4\u20137). A Parallel Algorithm for Clipping Polygons with Improved Bounds and a Distributed Overlay Processing System Using MPI. Proceedings of the 15th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing, Shenzhen, China.","DOI":"10.1109\/CCGrid.2015.43"},{"key":"ref_12","unstructured":"Ashan, M.K.B., Puri, S., and Prasad, S.K. (2024, January 12\u201315). Extending Segment Tree for Polygon Clipping and Parallelizing using OpenMP and OpenACC Directives. Proceedings of the 53rd ACM International Conference on Parallel Processing (ICPP), Gotland, Sweden."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Puri, S., and Prasad, S.K. (2014, January 9\u201312). Output-Sensitive Parallel Algorithm for Polygon Clipping. Proceedings of the 43rd International Conference on Parallel Processing (ICPP), Minneapolis, MN, USA.","DOI":"10.1109\/ICPP.2014.33"},{"key":"ref_14","unstructured":"Kullberg, G. (2019). Parallelization of Computational Geometry Algorithms. [Master\u2019s Thesis, Lund University]."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ashan, M.K.B., Puri, S., and Prasad, S.K. (2023, January 1\u20134). Efficient PRAM and Practical GPU Algorithms for Large Polygon Clipping with Degenerate Cases. Proceedings of the 2023 IEEE\/ACM 23rd International Symposium on Cluster, Cloud and Internet Computing (CCGrid), Bangalore, India.","DOI":"10.1109\/CCGrid57682.2023.00060"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., and Hoey, D. (1976, January 25\u201327). Geometric intersection problems. Proceedings of the 17th Annual Symposium on Foundations of Computer Science (FOCS 1976), Houston, TX, USA.","DOI":"10.1109\/SFCS.1976.16"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","article-title":"Algorithms for Reporting and Counting Geometric Intersections","volume":"100","author":"Bentley","year":"1979","journal-title":"IEEE Trans. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Hsu, K.-T., Sinha, S., Pi, Y.-C., Chiang, C., and Ho, T.-Y. (2011, January 5\u20139). A distributed algorithm for layout geometry operations. Proceedings of the 48th ACM\/EDAC\/IEEE Design Automation Conference (DAC), San Diego, CA, USA.","DOI":"10.1145\/2024724.2024765"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/2\/145\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:24:05Z","timestamp":1770960245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/2\/145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,10]]},"references-count":18,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,2]]}},"alternative-id":["a19020145"],"URL":"https:\/\/doi.org\/10.3390\/a19020145","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,10]]}}}