Exact basic geometric operations on arbitrary angle polygons using only fixed size integer coordinates

Abstract

As the semiconductor technology is scaling down to nanometer regime, accurate layout analysis requires operations with simulated contours of VLSI layouts which are non-rectilinear. The basic operations on non-rectilinear shapes include "intersection", "difference", "union", "find connected components" and "find boundary". Whatever precision one would choose for the representation of vertices of shapes A and B the exact representation of, say, A ∩ B would require an even higher precision. Consequently rounding of intermediate results of a chain of basic operations seems to be inevitable. The presence of rounding errors is unacceptable because the implementation of algorithms for all operations which involve topology, such as "find connected components", " find boundary", etc, becomes impossible or extremely complex We present a complete solution to the following problem: Let a VLSI design or a simulated through a lithography process image of a VLSI design be given by a number of two-dimensional point sets. Each point set consists of polygons with arbitrary (not necessarily 90°) angles and with vertices on an integer grid. Perform any amount of sequential basic operations so that: The resulting point sets are mathematically exact, that is no rounding errors are allowed. In particular the connectivity of the point sets remains intact, the boundaries remain undistorted and the statements like "A = (A \ B) ∪ (A ∩ B)", "(A \ B) is disjoint with B" and "A ∩ B ⊂ A" always hold. The amount of time and memory per one basic geometric operation on elementary polygons (trapezoids) is constant. For example it would not be an acceptable solution to represent the vertices of the new shapes which appear as a result of the operations of intersection, difference, etc, by unlimited length rational numbers.