Method and apparatus for identifying a path between a set of source states and a set of target states in a triangulated space
First Claim
1. A method of identifying a path in a design layout comprising a plurality of states, the path connecting a source state and a target state in the design layout, the method comprising:
- defining a triangulated graph in the design layout, the triangulated graph comprising a plurality of nodes, edges between certain pairs of nodes, and two orthogonal axes;
specifying at least one path that starts from the source state; and
iteratively specifying new paths by expanding previously specified paths in the graph until identifying a path that connects the source and target states;
wherein expanding a previously specified path comprises extending the previously specified path from a first state to a second state, wherein for at least one or more expansions, the second state comprises a line that is not aligned with the axes of the graph, the non-axis aligned line being part of an edge of the graph.
1 Assignment
0 Petitions
Accused Products
Abstract
Some embodiments of the invention provide a method for identifying a path in a design layout. Based on the design layout, the method defines a triangulated graph that has sets of source and target states and two orthogonal axes. The method specifies at least one path that starts from one state. It then iteratively specifies new paths by expanding previously specified paths in the graph until identifying a path that connects the source and target states. At least one of the expansions of a previously specified path is an expansion to a line that is not aligned with the axes of the graph.
-
Citations
18 Claims
-
1. A method of identifying a path in a design layout comprising a plurality of states, the path connecting a source state and a target state in the design layout, the method comprising:
-
defining a triangulated graph in the design layout, the triangulated graph comprising a plurality of nodes, edges between certain pairs of nodes, and two orthogonal axes; specifying at least one path that starts from the source state; and iteratively specifying new paths by expanding previously specified paths in the graph until identifying a path that connects the source and target states; wherein expanding a previously specified path comprises extending the previously specified path from a first state to a second state, wherein for at least one or more expansions, the second state comprises a line that is not aligned with the axes of the graph, the non-axis aligned line being part of an edge of the graph. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computer readable medium that stores a computer program for identifying a path in a design layout comprising a plurality of states, the path connecting a source state and a target state in the design layout, the computer program comprising instructions for:
-
defining a triangulated graph in the design layout, the triangulated graph comprising a plurality of nodes, edges between certain pairs of nodes, and two orthogonal axes; specifying at least one path that starts from the source state; and iteratively specifying new paths by expanding previously specified paths in the graph until identifying a path that connects the source and target states; wherein expanding a previously specified path comprises extending the previously specified path from a first state to a second state, wherein for at least one or more expansions, the second state comprises a line that is not aligned with the axes of the graph, the non-axis aligned line being part of an edge of the graph. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
Specification