cliff@centaure.UUCP (Cliff Dibble) (04/10/90)
I'm interested in algorithms for routing traces on printed circuit boards. I'd greatly appreciate any references to the subject. Thank you. uunet!centaure!cliff Cliff Dibble
grege@gold.GVG.TEK.COM (Gregory Ebert) (04/10/90)
In article <137@centaure.UUCP> cliff@centaure.UUCP (Cliff Dibble) writes: >I'm interested in algorithms for routing traces on printed circuit >boards. I'd greatly appreciate any references to the subject. >Thank you. > I think you are looking for Lee's algorithm. It was published in the Bell System Technical Journal, and applies to optimal routing of cross-country phone calls. Talk about technology transfer ! I believe the algorithm tries to establish a connection between 2 points by starting at each endpoint and working towards eachother.
flavio@mitisft.Convergent.COM (Flavio Rose) (04/11/90)
> I'm interested in algorithms for routing traces on printed circuit > boards. I'd greatly appreciate any references to the subject. > Thank you. > > uunet!centaure!cliff > Cliff Dibble Do you have access to a technical library? If so, look over the last few years' Design Automation Conference Proceedings. Also you might want to see the routing part of the bibliography in Alan Sherman's recent book on IC CAD published by Springer Verlag. Lee's algorithm is not the only one to look at. PC board routing is a complex subject.
waters@darla.sps.mot.com (Strawberry Jammer) (04/11/90)
In article <905@gold.GVG.TEK.COM> grege@gold.GVG.TEK.COM (Gregory Ebert) writes: {In article <137@centaure.UUCP> cliff@centaure.UUCP (Cliff Dibble) writes: {>I'm interested in algorithms for routing traces on printed circuit {>boards. I'd greatly appreciate any references to the subject. {>Thank you. {> { I think you are looking for Lee's algorithm. It was published in the { Bell System Technical Journal, and applies to optimal routing of { cross-country phone calls. Talk about technology transfer ! Lee's algorithm was the first published (BSTJ Aug. 1956). Turns out that the two problems have a lot in common. Lee's is still the basis for 90% of all routers used today. { I believe the algorithm tries to establish a connection between 2 { points by starting at each endpoint and working towards eachother. Not quite, a better analogy is pouring water on a floor then watching the wavefront cross as it spreads. Once the "target" get "wet" then you retrace the "flow" to the source and you have a vaid route. Obviously all of that is analogy, but it is quite close to what is simulated. Lee's algorithm is gauranteed to find a rout if one exists, but has numerous shortcomings. Look in the IEEE/ACM Design Automation Conference proceedings: The 1989 Proceedings can be found under: Library of Congress Cat no. 85-644924, ACM order no 477890, IEEE order no. 89H2734-2. Every conference since it was founded (26 years!) has had a section on routing algorithms of one kind or another. Routing is a tough problem in the real world. *Mike Waters AA4MW/7 waters@dover.sps.mot.com * You are in a twisting maze of little passages, all different.