2026-09-21T09:01:39Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/22372 2023-07-10 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Maddila, Sanjeev Rao 2011-05-07T13:37:44Z 2011-05-07T13:37:44Z 10000-01-01 1989 This thesis proposes a decomposition-based algorithmic paradigm, called planning with local experts, where the given global planning problem is decomposed into a set of subproblems that are each solved efficiently in a prescribed sequence and then the solutions of the subproblems are merged together. In the first part of the thesis, we investigate the problems of VLSI routing. In particular, we propose a way of decomposing the problem of routing in a general placement of rectangular modules into a set of subproblems of routing in junctions of L-, S-, T-, and X-shapes. We give non-trivial lower bounds on the channel widths of the associated channels of a junction. For example, we prove that $t\sb1$ + $t\sb2$ $\geq$ ${3\over2}$($d\sb1$ + $d\sb2$) for routing three-terminal nets in an L-shaped junction, where $t\sb1$ and $t\sb2$ are the widths, and $d\sb1$ and $d\sb2$ are the densities of the horizontal and vertical channels of the L-shaped junction, respectively. We also give routers for the general junctions, for the cases of routing two-, three-, and multi-terminal nets. For example, we prove that for routing two-terminal nets in an L-shaped junction $t\sb1$ + $t\sb2$ = $d\sb1$ + $d\sb2$, $t\sb1$ + $t\sb2$ $\leq$ ${3\over2}$($d\sb1$ + $d\sb2$) for the case of three-terminal nets, and $t\sb1$ + $t\sb2$ $\leq$ 2($d\sb1$ + $d\sb2$) for the case of multi-terminal nets. In the second part of the thesis, we investigate the problems of robot motion planning. In particular, we consider a technique to decompose the problem of moving a robot among a set of rectangles into a set of subproblems of moving the robot in certain localites. We give local experts for the local planning problems of moving a polygonal robot around a corner, and moving through a junction of general shape. For example, we give an $O$($m$ log $m$) algorithm for moving a convex $m$-gon around the corner in a corridor. Thus, using our decomposition scheme we develop an $O$($mn$ log $m$ + $n$ log $n$) algorithm for moving a convex polygon with $m$ corners among $n$ iso-oriented rectangles. Made available in DSpace on 2011-05-07T13:37:44Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9010946.pdf: 5985708 bytes, checksum: 137bdf30bedbd6d7e818bc4cc6897a1e (MD5) Previous issue date: 1989 Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:57:11Z Item is restricted indefinitely. Restriction data tranferred 2014-07-01T11:26:47-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission ETDs are only available to UIUC Users without author permission U of I Only AAI9010946 (UMI)AAI9010946 http://hdl.handle.net/2142/22372 eng Copyright 1989 Maddila, Sanjeev Rao Mathematics Engineering, Electronics and Electrical Computer Science Geometric planning for VLSI routing and robot motion text Electrical and Computer Engineering Electrical and Computer Engineering University of Illinois at Urbana-Champaign Dissertation Ph.D.