Spanning tree method for K-dimensional space

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 of the binary tree 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
• factorizing number of graph points by decreasing a number of components in the set of graph points until it becomes equal to a predefined specified program input parameter C, wherein partitioning includes checking a number of points k in a current set 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.

A system, comprising:

• a memory suitable for storing a program of instructions;
• and
• a processor communicatively coupled to the memory, the processor suitable for performing a program of instructions, wherein the program of instructions configures the processor to
• partition an input set of points into a binary tree of partitions so that each leaf partition of the binary tree 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
• factorize number of graph points by decreasing a number of components in the set of graph points until it becomes equal to a predefined specified program input parameter C, 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.

A system for partitioning an integrated circuit, comprising:

• a means for partitioning an input set of points into a binary tree of partitions so that each leaf partition has maximally a defined number of points;
• a means for making graph edges for the points, the graph edge means communicatively coupled to the partitioning means, wherein the graph edges means connects each point to maximum 2Kclosest points to make edges of the graph;
• and
• a means for reducing number of graph points communicatively coupled to the graph edge means, wherein the reducing means decreasing a number of components in the set of graph points until it becomes equal to a predefined specified program input parameter C, 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.