Efficient Scheme for Path Recognition fromIntegrated Circuit Layout

An efficient scheme for the centerline-basedpath recognition from an IC mask layout is presented. Unlikethe division-based methods, a tree-traverse-based approachis proposed. This new scheme can be realized as areverse procedure of the layout generation from wire routingtrees. Moreover, this scheme can handle complex allanglewires. Experimental results show that this schemehas nearly linear computational complexity yet generatesprecise results.