# GPU-Accelerated Algorithm for Polygon Reconstruction
## 1 Introduction  
Polygon reconstruction refers to the process of connecting a set of unordered line segments to form a closed polygon. This process is crucial in polygon Boolean operations and is widely used in fields such as computer-aided design (CAD), geographic information systems (GIS), and computer graphics [1]. These Boolean operations, including union, intersection, difference, and exclusive or (XOR), involve set operations on polygons in a two-dimensional plane. They play a vital role in many practical applications, especially in the field of integrated circuit electronic design automation (EDA). In particular, in the field of integrated circuit EDA, with rapid advancements in integrated circuit design and manufacturing, chip integration has substantially improved, leading to an increase in the number of devices on a single chip. Simultaneously, the shrinking feature sizes have imposed stricter demands on lithography technology. In advanced process nodes, in order to ensure that the patterns transferred onto the wafer are as consistent as possible with the original layout, resolution enhancement technology (RET) such as optical proximity correction (OPC) and inverse lithography technology (ILT) need to be applied. These techniques greatly increase the size and complexity of the layout polygons. Furthermore, with the ever-growing scale of layouts driven by higher chip integration, the computational burden of polygon Boolean operations has increased dramatically, making it increasingly difficult for existing algorithms to meet these new challenges. In existing research, polygon reconstruction algorithms are typically considered as part of polygon Boolean operations [2, 3, 4, 5]. Early algorithms often imposed strict restrictions onpolygon input and exhibited high complexity. As the number of polygons increases, their performance makes it hard to meet the practical needs. [PERSON] et al. proposed a polygon Boolean operation algorithm based on the Riemann-Stieltjes integral [1]. The algorithm achieves a theoretical complexity of \(O((n+s)log(n))\), where n represents the number of polygon edges, s represents the number of intersections between edges, and the algorithm demonstrates an approximately linear complexity of \(O(n^{1.08})\). In this algorithm, the authors integrated a simplified version of [PERSON]'s polygon reconstruction algorithm and achieved good performance [4]. However, with the continued shrinkage of process nodes and the rise in design complexity, the number of polygons in integrated circuit layouts has increased exponentially, reaching hundreds of millions in some designs, with each polygon containing hundreds or thousands of vertices, further exacerbating the computational challenges. The polygon clipping process can be divided into several sub-processes. In recent years, several parallel polygon clipping algorithms have been proposed, each improving overall performance by accelerating certain sub-processes. Some algorithms accelerate polygon Boolean operations through rasterization [6; 7; 8]. Other studies achieve parallelization by grouping polygons, where polygons within each group are clipped in parallel, but the clipping algorithm within each group is executed serially [9]. Reference [10] proposed an enhanced segment tree structure, which primarily accelerates the intersection detection and intersection filtering processes in polygon Boolean operations. Reference [11] parallelized [PERSON]'s polygon clipping algorithm and introduced three filtering techniques to reduce computational load as much as possible. This algorithm was applied to the clippings of two polygons with many vertices. However, in their study, the polygon reconstruction process still ran on the CPU. When dealing with two polygons rather than large-scale polygon sets, the time consumed by the polygon reconstruction process is not as significant. However, when handling extremely large polygon sets, the polygon reconstruction process also becomes a non-negligible part of the overall computation.