Patent ID: 6665850
Filing Date: 2003-12-16
Classification: G06F

Abstract:
A method for partitioning an integrated circuit, comprising:partitioning an input set of points into a binary tree of partitions so that each leaf partition has maximally a defined number of points; making graph edges for the points by connecting each point to its closest point in every of 2Ksubspaces; and reducing number of graph elements to predefined value, wherein partitioning includes checking a number of points k in a current partition to determine if the number is greater than the maximally defined number of points M, if it is, a median is calculated for every K coordinate and a coordinate nd which has a greatest quadratic deviation is chosen as the coordinate by which the partition is divided into two smaller partitions, every point that has nd coordinate value less or equal to the value of its median medd is put into a first child partition and all other points into a second child partition.