Short path search using tiles and piecewise linear cost...

Details Short path search using tiles and piecewise linear cost... Short path search using tiles and piecewise linear cost...

2006-11-21

2006-11-21

Thompson, A. M. (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

07139992

ABSTRACT:
A method for finding shortest paths is disclosed which uses a piecewise linear cost model to guide the search of through a compact tile graph and to ensure that a shortest path may always be found in a computationally effective manner. Cost function propagation from tile segment to tile segment is used to search for a target location from a source location through a region, and the shortest path is found through tracing backwards using the cost functions calculated during the searching. Linear minimal convolution is used to facilitate the cost function propagation.

REFERENCES:
patent: 5511015 (1996-04-01), Flockeneier
patent: 5748844 (1998-05-01), Marks
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5841664 (1998-11-01), Cai et al.
patent: 6175950 (2001-01-01), Scepanovic et al.
patent: 6182272 (2001-01-01), Andreev et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6292928 (2001-09-01), Yamaguchi et al.
patent: 6324674 (2001-11-01), Andreev et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6353918 (2002-03-01), Carothers et al.
patent: 6415427 (2002-07-01), Nitta et al.
patent: 6477692 (2002-11-01), Marchenko et al.
patent: 6665852 (2003-12-01), Xing et al.
patent: 6763512 (2004-07-01), Xing
patent: 6792587 (2004-09-01), Xing et al.
patent: 2002/0104061 (2002-08-01), Xing et al.
Sellen et al., “Direction weighted shortest path planning”, May 21-27, 1995, Conference on, Digital Object Identifier 10.1109/ROBOT.525552, vol. 2, pp. 1970-1975□□.
McAllister et al., “A compact piecewise-linear Voronoi diagram for convex sites in the plane”, Nov. 3-5, 1993, Proceedings., 34th Annual Symposium on,Digital Object Identifier10.1109/SFCS.1993.366829, pp. 573-582 □□.
Arnold, M. H. and Scott, W. S., “An Interactive Maze Router with Hints,” 25th ACM/IEEE Design Automation Conference, 1988, Paper 41.4, pp. 672-676.
Tsai, Chia-Chun et al., “An H-V Alternating Router,” IEEE Transactions on Computer-Aided Design, vol. 11, No. 8, Aug. 1992, pp. 976-991.
Margarino, A. et al., “A Tile-Expansion Router,” IEEE Transactions on Computer-Aided Design, vol. CAD-6, No. 4, Jul. 1987, pp. 507-517.
Liu, Le-Chin E. et al., “Chip-Level Area Routing,” International Symposium on Physical Design, Proceedings of the 1998 International Symposium on Physical, Monterey, CA, 1998, ACM Press, NY, NY pp. 197-204.
Cong, Jason et al, “An Implicit Connection Graph Maze Routing Algorithm for ECO Routing,” ACM SIGDA proceedings 1999, Session 3B: Routing, 5 pp.; [online] Downloaded from the Internet May 14, 2002, URL: <http://www.sigda.org/Archives/ProceedingArchives/Iccad/Iccad99/papers/1999/iccad99/pdffiles/03b—2.pdf>.
Dion, J. and Monier, L. M., “Contour: A Tile-based Gridless Router,” WRL Research Report 95/3, Digital Western Research Laboratory, Palo Alto, CA, Mar. 1995, 30 pp. [online] Downloaded from the Internet May 14, 2002, URL: <ftp://gatekeeper.research.compaq.com/pub/DEC/WRL/research-reports/WRL-TR-95.3.pdf>.
Wu, Ying-Fung et al., “Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles,” IEEE Transactions on computers, vol. C-36, No. 3, Mar. 1987, pp. 321-331.
Zheng, S. Q. et al., “Finding Obstacle-Avoiding Shortest Paths Using Implicit Connection Graphs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 1, Jan. 1996, pp. 103-110.

Affiliated with

Also associated with

Rating

Short path search using tiles and piecewise linear cost... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Short path search using tiles and piecewise linear cost..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Short path search using tiles and piecewise linear cost... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3635206