随着集成电路制造工艺尺寸的迅速缩小,在使用现有的光刻技术时,光波将发生衍射,导致版图图形产生较大失真。目前双成像光刻(double patterning, DP)技术是解决这一问题的最有效的方案之一。在双成像光刻中,一项必要的工作是版图分解,即将版图中多边形分解为更简单的图形的集合。现有的多边形分解算法不适合应用于双成像光刻,会产生工艺无法接受的薄片,覆盖误差会导致图形断开,与双成像光刻中的版图分解的目标也不同。本文提出一种新的版图分解算法,通过引入交叠,消除薄片的产生；同时解决由于覆盖误差引起的图形断开问题；减少分解后的矩形数目,从而减少双成像光刻中颜色分配后的冲突总数,适合用于双成像光刻技术。首先,介绍双成像光刻技术和多边形分解算法的背景概况,从而提出本文的版图分解算法和主要贡献。通过比较和现有的各种算法分别对版图中常见的一些多边形例子进行分解的情况,从而说明本文的算法优胜的方面。然后,对本文算法针对的分解问题进行限定,定义了与算法相关的概念。在这个基础上具体阐述本文所提出的算法。最后,通过实验验证本文算法功能的正确实现,并通过将本文算法和不引入交叠的算法等进行比较实验,从而证明本文算法的有效性,适合用于双成像光刻技术。