Patent ID: 8490030

Claim:
A method of characterizing a plurality of clips of an integrated circuit layout for clustering, at least one clip including multiple polygons, the method comprising: (a) identifying polygons of a first clip and a second clip; (b) initializing states of all polygons in the first and second clips as unmatched; (c) for a first unmatched polygon in the first clip, finding a second unmatched polygon in the second clip where a distance metric between the first and second unmatched polygons is minimized, the distance metric being computed using a processor by integrating differences of radial and angular functions of the first unmatched polygon in the first clip and the second unmatched polygon in the second clip, the distance metric providing a quantitative measure of similarity; (d) when the distance metric is less than a predefined threshold, setting the first and second unmatched polygons as a matched pair, and setting states of the first and second unmatched polygons as matched; (e) when the distance metric is not less than the predefined threshold, setting the state of the first unmatched polygon as unique; (f) repeating steps (c), (d), and (e) for each remaining unmatched polygon in the first clip; (g) calculating matched distances for all matched pairs; (h) calculating unmatched distances for all unique polygons; (i) computing a total distance for the first and second clips by summing all matched distances and all unmatched distances; (j) repeating steps (b)-(i) for each of eight transformations of the first clip, a transformation being a reflection or a rotation of the first clip; and (k) determining a minimized total distance metric from the eight transformations, wherein the minimized total distance determines whether the first and second clips should be clustered, wherein the method is performed by a computer.