Rectilinear covering method with bounded number of rectangles for designing a VLSI chip

摘要

A method for creating a rectilinear non-convex polygonal output representative of a component used to build a VLSI circuit chip from a plurality of points corresponding to a plurality of components of the chip includes: covering the plurality of points with a set of rectangles; creating a Voronoi diagram for the set of rectangles; forming a nearest neighbor tree for the Voronoi diagram; connecting a selected set of the rectangles corresponding to the nearest neighbor tree into a non-convex rectilinear polygon; and applying the non-convex rectilinear polygon to build the VLSI chip.