Patent ID: 8117569

Claim:
A computer implemented method for constructing a minimum spanning tree for an integrated circuit product, comprising: using at least one processor for performing a process, the process comprising: performing a looping procedure to identify a point-pair for relevant points on the integrated circuit product to add to a minimum spanning tree, wherein the looping procedure proceeds until all of the relevant points have been included in the minimum spanning tree, and the looping procedure comprises: identifying at most two nearest neighbors, which are not yet in the minimum spanning tree, of a first point that already exists in the minimum spanning tree for each iteration of the looping procedure by identifying a first nearest neighbor of the at most two nearest neighbors for the point-pair and a second nearest neighbor of the first nearest neighbor by using one or more metrics; and determining whether a point in the point-pair forms a loop with one or more existing points that already exist in the minimum spanning tree by at least removing the point-pair from a data structure and by at least identifying a replacement point-pair for the point-pair from the data structure where the point is determined to form a loop with the one or more existing points.