Patent Document ID: 8296702
Application ID: 12686412
Patent Status: 1

Claim One:
1. A method for creating a rectilinear non-convex polygonal output representation of a component used in building of a Very Large Scale Integrated circuit (VLSI) chip from a plurality of points, each of the points representing a plurality of components, the method comprising: a) covering said plurality of points with a set of rectangles; b) finding the nearest rectangle for each rectangle forming said set, creating a Voronoi diagram applicable to said set of rectangles, forming a nearest neighbor tree for said Voronoi diagram, and finding in said nearest neighbor tree a nearest neighbor rectangle for each rectangle forming said set; c) creating a non-convex rectilinear polygon by connecting each rectangle to its nearest neighbor rectangle; and d) using a computer to apply said non-convex rectilinear polygon to build said VLSI chip.