Importance

Loading Importance Indicators...

Abstract

Some embodiments of the invention provide a method for propagating a first piecewise linear function (PLF), which is defined over a first state, to a second state, which is a point. In some embodiments, the space includes a set of states and a transition map that specifies a set of states that can be reached from each particular state. For instance, in some embodiments, the space is a graph that includes points, lines, and surfaces. The method projects vectors from points on the first state that are locations of inflection points in the first PLF. If the second state is between two projected vectors that emanate from a vector-emanating point on the first state, the method then computes a cost at the second state that equals the sum of the cost of the first PLF at the vector-emanating point and the distance between the vector-emanating point and the second state in the design layout. On the other hand, if the second state is between two projected vectors that emanate from the different points on the first state, the method identifies the length of a first line that is parallel to the two projected vectors and that is between the second state and a termination point on a second line connecting the two points on the first state from which the two projected vectors emanate. The method then computes a cost at the second state that equals the sum of the identified length and the cost of the first PLF at the termination point.

Loading the Abstract Image...

First Claim