Creating and Exploiting Flexibility in
Rectilinear Steiner Trees
Elaheh Bozorgzadeh,Ryan Kastner,and Majid Sarrafzadeh Abstract—The global routing problem decompos the large,complex routing problem into a t of more manageable subproblems.The high correlation between the output of the global router and the detailed router enables the designer to efficiently u the global route to refine the design quickly before running full detailed route.Hence,routability of the global routing solution is the key factor.The routability of the circuit depends on the congestion of the routing.In this paper,we study Steiner trees in terms of routability.We introduce the notion offlexibility–a geometric property associated with Steiner trees.We show that theflexibility of a Steiner tree is related to its routability.The main contribution of this paper is an algorithm which takes a stable Steiner tree as an input and maps it to a moreflexible Steiner tree.Any existing Steiner tree algorithm can be ud for the initial construction of the Steiner tree.Experiments with a global router on a subt of nets show that routing congestion is improved by approximately20%locally throughout the region where tho nets are routed.
I.I NTRODUCTION
W ITH today’s silicon technology,not only has the effect of inter-connect delay on total path delay become significant,but also dominant.The router must have good controllability and predictabil-ity on congestion and timing issues,so that the design can converge on timing and interconnect without excessive routing iterations.
A standard cell router needs to handle a very large number of small standard cells.Current standard cell routers are mainly area-bad gridded routers.The routers extensively employ rip-up and reroute (arch and repair)algorithms to clean up design rule violations.The advent of DSM(Deep Sub-Micron)technology has greatly compli-cated the standard cell routing procedure.
Routing usually involves two steps:global routing and detailed rout-ing.Global routing creates an approximate path for every interconnect, even though this path is not yet physically exact.Detailed routing then follows,determining the width and spacing needed for each different metal layer.The global router should consider a number of different metrics including–but not limited to–minimizing the delay of the each net,reducing the size of the chip,minimizing the number of vias and distributing the routes equally across the routing area[19].The important problem facing global routing is to develop sub-solutions such that they can be solved by detailed router.A global routing so-lution with minimum delay and chip size accomplishes nothing if the detailed router can notfind a solution.Henc
e,routability of the global routing solution is the key factor.Routability of the circuit depends on the congestion of the routing.Most global routers u congestion maps to help designers understand the results of global routing.If the design appears congested after the global route,designers alter the top levelfloorplan or placement of cells inside the block to get a better congestion before starting a detailed routing job.
Steiner tree construction is an esntial part of global routing(the problem is formally defined later in Section II).The early t of Steiner
This work was partially supported by NSF under Grant#CCR-0090203. Elaheh Bozorgzadeh and Majid Sarrafzadeh are with Computer Sci-ence Department at University of California,Los Angeles.(email: elib,majid@cs.ucla.edu)
Ryan Kastner is with Department of Electrical and Computer Engineering at University of California,Santa Barbara.(email:kastner@ece.ucsb.edu)tree algorithms focud on minimizing the total wire length as the ob-jective(e[19]for an overview).As wire delay has become increas-ingly more important,Steiner tree algorithms have focud on mini-mizing the delay of the net.Recently,there has been much focus on algorithms which simultaneously consider buffer inrtion,wire sizing and/or Steiner tree construction[11],[15],[18].
Typically,critical nets are a small subt of the overall number of nets.However,the number of critical nets are increasing with today’s DSM technology.The delay of non-critical nets is not crucial to the performance on the circuit.Therefore,the nets should be routed in a manner which increas the likelihood that the detailed router canfind afinal,valid solution.Yet,we do not know of any previous Steiner tree algorithms which explicitly consider routability.Mostly routability is referred to as the density of routing edges in global routing.There exist many different global routing algorithms both in industry and rearch.In most of the techniques,the congestion is handled itera-tively.There are other techniques which are not bad on net ordering. In[5],a Steiner-tree bad global router is prented.The propod algorithmfinds a weighted Steiner tree for a net while the weight of a region reprents the demand of the region.The aim is to optimize the length and density simultaneously.In[6],a performance-driven Steiner tree algorithm is propod.The objective is to minimize the delay function of Steiner tree.Global routing problem is formulated as multiterminal multicommodityflow problem.The objective is to max-imize the overall routability by minimizing the edge congestion for a t of nets.In[3],an approximation algorithm for multi-commodity flow is ud for global routing which can reduce the congestion sig-nificantly.In that paper,it is assumed that the algorithm can query a subroute to give a Steiner tree of a net withfixed length.
In this work,we study Steiner trees in terms of routability.We in-troduce the notion offlexibility–a geometric property associated with Steiner trees.Flexibility in routing edges has been exploited in many of the abovementioned existing rearch to improve the routing con-gestion.To the best of our knowledge,there has not been any work which tries to maximize theflexibility in routing trees.In this work, our focus is not to propo a new global routing algorithm or to de-velop a new algorithm to construct a new Steiner tree but to introduce and understand the property offlexibility for Steiner trees.With no deep understanding offlexibility,this property has been exploited(not fully)in veral global routing techniques.For example,flexibility in Steiner trees has been exploited in the timing-driven global routing propod in[10].The global router tries to reduce routing conges-tion by taking advantage of different possible routes for edges called soft edges.We show that theflexibility of a Steiner tree is related to its routability.Specifically,aflexible tree is less prone to being routed through a congested region.We demonstrate this concept by construct-ingflexible trees in a state-of-the-art global router.Global
[10],[8])can take advantage offlexibility inflexible routing trees to reduce the congestion locally.
The main contribution of this paper is an algorithm,which takes a Steiner tree as an input and produces a moreflexible Steiner tree.The only restriction on the initial tree is that it must be stable(st
ability is defined in Section II-B).The new,flexible tree is guaranteed to have the same total length.Any existing Steiner tree algorithm can be ud for the initial construction of the Steiner tree.As an example,our technique to map one Steiner tree to another tree with same length but moreflexibility can be ud in querying the subroutine to obtain new Steiner trees for the nets in the approximation algorithm described in [3].Here it means that new Steiner tree might be found by changing the route offlexible edges for the net only.As a conquence,our algorithm can be applied or integrated into global routing algorithms to reduce the congestion locally.The preliminary version of this work has been published in DAC2001[7].In[7],only the concept offlexibility
in global routing is propod.The detailed analysis of creating and
exploitingflexibility is prented here in this work.
The paper proceeds as follows:In Section II,we give some basic
routing definitions,define the minimum Steiner tree problem and some
associated properties of Steiner trees includingflexibility.In Section
III,the problem of generatingflexibility in Steiner trees is formulated.
Then our algorithm is described,which takes an existing Steiner tree
as input and increas itsflexibility.In Section IV,experimental re-
sults which study the impact offlexibility during global routing are
prented.We conclude and give some possibilities for future work in
Section V.
II.P RELIMINARIES
英语同步答案A.Global Routing Definitions
A grid graph is a graph G(V,E)such that each vertex corresponds
to a point in a plane(an example is shown in Figure1).A net
=is an unordered t of points on a grid graph.A single point of the net is referred to as a ter-
minal.A routing of a net is a t of grid edges such that the terminals
are fully connected.Integer grid routing is assumed.The route edges
of a net are the t of edges ud in the routing of that net.
A global bin is a rectangular partition of the chip.By partitioning
the chip into many rectangular regions and placing the cells into the
regions,we have a placement using global bins.The boundaries of the
global bins are global bin edges.
Fig.1.(a)Placement of Cells into Global Bins.(b)The Corresponding Grid Graph.
In this paper,we assume that a global placement of cells and their
interconnections are given by some placement engine.Each cell is
assumed to be placed in the center of the global bin.The global bins
and edges can be transformed into a grid graph(e Figure1).The
interconnections between the cells can be modeled by nets.
The capacity(also known as supply)of edge is.It is the maxi-
mum number of nets that can be routed over.is afixed value that
is bad on the length of the edge and the technology ud in creating
the chip.The routing demand of,specified as,is defined as the
number of route edges crossing edge.Similarly,the demand of a
vertex is.Here the demand corresponds to the number of routes
that pass though the vertex(equivalently the global bin).An edge
is overflown if and only if the.Formally,the overflow of an
edge is:
if
otherwi(1) is a threshold value which allows to go above without an overflow penalty.is ud since you can often route up to nets though neighboring bins without affecting the congestion of tho bins.is usually a small constant(between2-5).Using the global bin and global edge notation,the total overflow of a routing is:
(2) where is the number of bin edges.The total overflow reflects the shortage of routing resources for a particular t of edge capacities. The objectives of our global router is a linear function of the overflow of a route and the route length.Our industrial experience shows that total overflow is a good measure of congestion[8].
B.Rectilinear Steiner Tree
Given a net(t of nodes called terminals of the net)embedded in a grid graph,a rectilinear Steiner tree(RST)is a tree interconnecting the terminals of and some arbitrary points
.The points are known as the Steiner points(also called Steiner nodes)of.The rectilinear Steiner tree problem is tofind a rectilinear Steiner tree of minimum length(Steiner Minimal Tree).The length of a Steiner tree is the sum of the length of the edges of the tree.In rectilinear Steiner tree problem,the distance is defined in metric (rectilinear metric),in which the distance between two nodes is the sum of the difference of their-coordinate and-coordinates.The construction of a Rectilinear Steiner Minimal Tree(RSMT)has been given much attention and shown to be NP-Complete.[14]. Formally,a gment is a horizontal or vertical line gment connect-ing its two end points in the plane.Degree of each point is at most .Steiner points have the edge degree of -point is a point with degree with non-collinear gments that is not a terminal. Two points are directly connected if they are connected by a quence of one or more gments including only corner-points.Such a route has stairca shape.
For any given rectilinear Steiner tree,there is a corresponding tree graph(),which is called topology.Vertices of correspond to the terminals and Steiner points of RST.Note that the corner-points are not vertices of the graph.Edge connects vertices and iff the corresponding points are directly connected in.As long as the edges between the vertices remain consistent,the topology is considered unchanged.In a given RST,location of Steiner nodes can change such that topology does
not change(e Figure3).Similarly in graph,the degree of vertices is bounded by.If the Steiner point has edge degree of,it is called cross-point.T-point is a node with degree in which one of incident edges is perpendicular to the other two incident edges.
In[2],Hwang et al.define two different transformations for rec-tilinear Steiner trees:flipping and sliding.Each transformation maps one such tree to another without moving the positions of the terminals and without increasing the length of the tree.Depending on the di-rection of transformation,there are different slides andflip moves. In slide,a gment perpendicular and incident to parallel gments is replaced by new gment which is still perpendicular and incident to the parallel gments.Slide transformation and Flip transformation
are shown in Figure3.
Stable RST Unstable RST
新叶古村
Bounding box
of edge e
Fig.2.Examples of Stable and Unstable RSTs.
什么是老板Ho et al.introduced the notion of stability under re-routing in an RST[16].A RST is stable if there is no pair of edges such that their bounding boxes interct or overlap except at a common endpoint(if any)of the two edges.Equivalently,a stable RST will not have over-laps when the edges are routed with minimum length.From this point forward,any reference to a RST assumes that the tree is stable.Figure 2shows examples of stable and unstable RSTs.
C.Pattern Routing
Since we are focusing on routability,we define the cost of the Steiner tree as a linear function of the overflow and route length.We need to assign a routing(rectilinear route)to the edges which are nei-ther vertical nor dge in Figure2).We choo to pattern route such edges.Pattern routing is the notion of using pre-defined patterns to embed an edge on the grid graph.Usually the are simple patterns such as a L-shaped–1-bend–or a Z-shaped pat-tern–2-bends,route restricted wit
hin bounding box.In this paper,we restrict our pattern route definition to L-shaped or Z-shaped patterns. Pattern routing has many benefits.First,it has a lower runtime com-plexity when compared to maze routing[13]–a commonly ud rout-ing algorithm.Second,a pattern routed net has small delay since it introduces a constant predetermined number of vias and routes the net with minimum wirelength.Finally,by properly choosing a subt of nets to pattern route,the global routing solution is more predictable without hindering the overall quality of the routing solution;this gives high level CAD placement engine,floorplanner)higher ac-curacy when estimating routing metrics such as congestion,routing area and wirelength[8].
D.Flexibility
In this ction,we define the property offlexibility.We argue that flexibility relates to the routability of the Steiner tree.
Aflexible edge is an edge by which two nodes are directly connected with more than one gment.Therefore theflexible edge has one or more corner-points(stairca shape,L-shaped or Z-shaped).Flexible edges allow more than one minimum length route.If an edge is routed with minimum rectilinear length,the route is contained within the bounding box of.An inflexible edge has o
nly one minimum length routing.Given aflexible edge with coordinates of its two end-points as and,and are defined as follows:
(3)
(4)
and are called the-coordinate and-coordinate of edge, respectively.The number of distinct two-bend routes(equivalently Z-shaped)with minimum length is and the number of distinct one-bend(equivalently L-shaped)routes with minimum length is.In this paper,theflexible edges are shown as diagonal edges in thefigures to show that there are more than one possible rectilinear routes for such an edge.
Looking at Figure3,we show two rectilinear Steiner trees for the same net.One tree has someflexible edges while the other has only inflexible edges.Both trees have the same rectilinear length and topol-ogy.Assume that the shaded area is congested.Theflexible tree is able to avoid the congested region while the inflexible tree has no choice but to be routed through the congested area if each edge is routed with minimum rectilinear length.
We need to define a function which evaluates theflexibility of a given edge.The function should reflect the routability of the
edge.
s1
(a)(b)
T1T2
Fig.3.(a)RST With Flexible Edges.(b)RST With No Flexible Edges.
Additionally,a function corresponding to edge should have the following properties:
when or.
is a monotonically increasing function of and.
Two suggestedflexibility functions,and,are shown in Equa-tions5and6.
if or
Otherwi
(5)
(6) Function corresponding toflexible edge returns the value equal to half of the length of the bounding box of edge.The value of function corresponding to edge is the area of the bounding box of edge.Theflexibility of a Steiner tree is computed by summing theflexibility over all the edges.Equation7defines theflexibility on a subtree.A number of other functions can be introduced.
(7)
III.C REATING F LEXIBILITY IN R ECTILINEAR S TEINER T REES In this ction,we prent an algorithm which maps a given rectilin-ear Steiner tree to another RST with maximum increa in theflexibil-ity of the Steiner tree.First,we formally define the problem.Next,we describe our algorithm to maximize theflexibility of a given RST.Our algorithm solves the problem optimally subject to a t of constraints.
A.Problem Formulation
Given a stable RST,
Map it to a stable RST such that,the increa inflexibility of the RST,is maximized,
Subject to:
-Topology and stability remain unchanged,
-Each edge is routed with minimum rectilinear length,
-No edge is degraded inflexibility1.
Theorem1:In a stable RST,if the Steiner point has aflexible edge,the degree of is.Only oneflexible edge can be incident to a Steiner point.
Proof:More than oneflexible edge cannot be incident to the Steiner point due to the stability of the RST.The examples of stable and non-stable Steiner points in a tree are shown in Figure4.唯美清纯
No Steiner cross-point can have aflexible edge.Steiner point with edge degree is either a T-point(not
incident to aflexible edge)or including aflexible edge.When a Steiner point is incident to aflexible edge,we refer to that point as aflexible point(e Figure4).
Definition:The Steiner point in a stable RST is movable if we can move to any other location while keeping the RST stable and the
T-point Stable P
Unstable P Fig.4.Examples of Stable and Unstable Point
in a RST
2
45
6
Fig.5.Six Different Directions for Moving Steiner Point p.
topology unchanged.Similarly,an edge is movable if can be moved and the resulting RST remains stable with no change in topology.Theorem 2:There is no single movable node in a stable RST.At least two adjacent nodes (two Steiner nodes)have to be moved.
Proof:In order to make gment more flexible,can move in six different directions (e Figure 5).Cha
nging the connectivity between Steiner nodes and terminals is not allowed.To discover the requirements,the moving of node along all possible directions is investigated.Figures 5,and 7are referred during the proof.By moving towards any of directions ,the RST gets unstable unless the topology of the RST changes.In Figure 6,point is moved towards direction .At most one edge would be located on the right side of and the rest will be on the left side of or along the vertical borders.Only one of the edges on the left side of can be flexible and only one edge can be horizontal.In all different configurations of the edges the RST would be unstable.
If node is moved towards direction ,no edge in direction should exist.Otherwi,by moving point ,RST gets unstable.Therefore,point cannot be a T-point with the collinear incident edges perpen-dicular to gment .By moving point to point in direction ,
This assumption slightly simplifies the problem.The
problem can be ex-tended without it.
Fig.6.Unstable
Move
P
P
stable
stable
Fig.7.Moving Steiner Point
Along Direction .
脑部磁共振
the tree is unstable unless point is movable in direction as well.By
moving
in parallel with in direction ,tree would remain stable while the topology also remains unchanged (e Figure 7).This shows that two incident nodes (i.e.an edge)have to be moved.In other word,moving one node results in moving one of the nodes incident to that.Basically point needs to be a T-point or flexible point where in both cas the two collinear incident edges are along direction .Moving towards direction is similar to direction .
Note that an edge can also be moved only from one end point.When an edge is moved from both ends,the incident edges to both end nodes of the edge are moved from one end.We do not consider such edges as movable edge.We will e later such edges can be flexible candidates or parallel edges of movable ts.
Theorem 3:An edge in a stable RST is movable along direction if both vertices incident to the gment
are Steiner points with edge degree .
have incident edges towards the same direction .That is the direction of move for edge
.
Fig.8.Movable Segment .
Proof:Consider Figure 8.According to the proof of Theorem 2,
an edge is movable in either horizontal or vertical direction while both ends are moved.When node is moved towards direction ,there has to exist an edge incident to the node towards direction .If there is no edge incident to towards direction ,the bounding boxes of the edges incident to will overlap after edge is moved toward direction .That violates stability of RST.Therefore,there must be an edge incident to in direction .Since RST is stable and edge degree of is three,the other edge incident to is in darkened region shown in Figure 8.Therefore,Steiner point has an incident edge towards
direction and the edge
is movable.According to Theorem 3,the conditions under which an edge can be moved is similar to slide transformation in rectilinear Steiner tree.The difference is that in movable edge topology cannot change.Therefore by moving the movable edge in a given rectilinear RST,it is mapped to another RST with same topology.We can refer to the movable gment as sliding gment as well.
Corollary 1:On a movable edge slide transformation can be ap-plied while topology does not change.
A subtree consisting of movable gment and a t of edges adja-cent to ,,can be defined as a Movable Set
.,
(c)(d)
Fig.9.Movable Set With Movable Edge
.
Fig.10.Flexible Segment Generated by Algorithm Generateflexible Tree.
,
,
isflexible candidate,
,
where is the t of all adjacent edges to including gment.
熬梨汤的做法consists of three different edge subt.is the t of the two parallel edges according to Theorem3.is the movable gment, i.e..is the t offlexible candidates among the adjacent edges to .By moving edge theflexibility of edges in increas.is the t of edges excluding the ones belonging to,,and.For an example of a movable t,e Figure10.
The movable t is a subtree with leaves and two internal nodes. It is similar to definition of full component in Steiner tree.Full com-ponent is defined as a subtree with leaves of terminals[2].However, in a movable t,the leaves need not to be the terminals.
Corollary2:If the leaves of subtree of movable component are the terminals,the movable t is a full rectilinear Steiner component with 4nodes.
B.Algorithm
Figure9shows different movable ts.The movable ts have different subts of edges in.The edges adjacent to are different in terms offlexibility.The movable t in Figure9(a)has no flexible The other movable ts have at least oneflexible candidate.Theflexible subts()are in
Figure 9(b),in Figure9(c)and in Figure9(d).Edge is already aflexible edge.However by moving gment theflexibility of can increa.Edges,,and becomeflexible after gment is moved.In Figure9(a)moving gment produces no additional flexibility.In the other cas,theflexibility of the RST increas by moving gment.This implies that at least oneflexible candidate has to exist in a movable t in order to increa theflexibility of the RST by moving the movable edge.
Theorem4:In a stable RST,by moving a movable edge,flexible
edge(s)can be generated orflexibility of an edge(s)can increa if at
least one of the two vertices incident to the movable edge is aflexible
node with an incident edge towards the moving direction.
Proof:If both endpoints of the moving edge in a movable t
are T-points,noflexible edge can be generated by moving the movable
edge.
In order to increa theflexibility of a RST,wefirst need to arch
for movable ts which have the potential to generateflexible edges.
Movable ts in a RST can be found in,where is the the edge
t of the Steiner tree.According to Theorem3,each edge is checked
whether it is movable with incidentflexible candidate.
When a movable t is found,the movable gment can move along
the parallel edges.The maximum movement is the minimum length
of the two parallel edges incident to the movable gment.In other
words,this is the maximum range for sliding transformation on mov-
able gment without changing the topology of RST.In Figure10,the
maximum length of sliding is where and are the length of the parallel edges.Since topology should not change,
the gment can move as far as one grid before it reaches the end node
of any of the two parallel edges.According to Theorem3,by moving
a movable edge,theflexibility of the RST improves without changing
the wirelength and topology.However,by maximizing theflexibility
of a movable t,we may restrict theflexibility of another movable t.
We discuss this situation,called overlap,next.
C.Overlap in Movable Sets
Once every individual movable t is found in a given RST,the ques-
tion is:Are the movable gments independent and by moving all of
them,can maximumflexibility be obtained?In order to answer the
question,we need to e how movable gments can overlap.
When there is no overlap,we easily compute theflexibility func-
tion for each moving gment.Since theflexibility function is mono-
tonically increasing in terms of-coordinate and-coordinate of the
edges,the maximum of occurs if each moving edge is moved to
its maximum limit.Unfortunately,theflexibility cannot be computed
independently for two overlapping gments.
Two movable gments have overlap with each other in either of the
two following cas:
1)The movement of movable edge is limited by the movement of
the other movable edge(Figure11).
2)Moving the movable edge increasflexibility of an edge
while the movement of some other movable gment leads to
a decrea in theflexibility of(Figure12).
Two movable ts interct if their corresponding edge ts share a
规训
common edge.There are six possible interctions between any two
写山的诗句movable ts.Only three of them cau overlap between the gments.
Let and be two movable gments and and be the pair of incident nodes for gment and respectively. The six different interctions between the two ts are as follow: 1).
Segment and gment have a same parallel edge.
a).
The moving direction of both must be the same.Other-
wi the degree of cannot be3.This is overlap type.
This ca is shown in Figure11(a).In order to have the
same topology and maximize theflexibility,the amount of
movement for each gment would be:
b).
is the t of nodes incident to.If the moving direc-tion of both is the same,no overlap would occur(Figure11
(c)(d)
Fig.11.Interction Between Two Movable Sets With Shared Parallel Edge.
( 1 ) ( 2 )
Fig.12.Interction When a Parallel Edge Being Another Moving Edge.
(b)).When they move in opposite directions,overlap can
occur.The two cas in which overlap occur are shown in
Figure11(c)and(d).
In Figure11(d),the gment overlaps with as well.
This ca is complicated will be discusd later.This is a
combination of overlap types and.
In the ca shown in Figure11(c),overlap can occur if the
condition below holds.
This is overlap type.
2)
The moving edge is theflexible edge of gment.This is same as interction.
3)
The movable edge of a t is a parallel edge of another t.The two cas are shown in Figure12.Thefirst ca does not over-lap,but the cond one is similar to the overlap shown in Figure 11(d).
4)
Such a ca will not happen since the RST is stable.
5)
The parallel edge of is aflexible edge in t.The configu-ration is same as the one shown in Figure12
(2).
6)
This ca is shown in Figure13.Figure13(a)shows when two ts have the sameflexible edge in the same moving direction.
In this ca there is another movable t between tho,which has overlap ca with both of them.This is a chain of ca
with overlap type.There is no overlap in the ca shown in Figure13(b).
According to the study on all possible interction between the two movable ts,there are two types of overlap that can occur: Overlap Type1:It occurs when a parallel edge of two movable ts is the same and inequalities mentioned in interction1hold.
Overlap Type2:It occurs whenflexible edge of a movable g-
Fig.
s1
w1w’1
Fig.14.Maximum Overlap of a Movable Set with Other Movable Sets.
ment is a parallel edge of the other moving t.
Theorem5:Each movable gment t can have at most two over-laps of type1and two overlaps of type2.
Proof:Since each movable t has two parallel edges,each can have overlap(type)with another movable t.A movable t has at most twoflexible edges.Therefore,at most two overlaps of type can occur byflexible edges being the parallel edges of the two other movable ts.Overlaps more than leads to edge degree for the steiner nodes at two ends of movable edges which contradicts with the properties of movable t.
In Figure14,movable t overlaps with gments ,,and.Two of the overlaps are overlap type and the other two overlaps are of type.
When movable ts are being found in a RST,overlaps among the movable t can be detected as well.When an edge is being re-visited it means that the edge has already been recognized as a member of another movable t which has already been found.In such a ca the algorithm checks
whether such an interction generates overlap. Since each edge can participate at most in movable ts according to Theorem5,the complexity of the algorithm tofind the movable ts and their overlap still remains.Thefirst loop of the pudo-code shown in Figure16finds the movable ts and the overlaps among the ts.
In both types of overlap,we need to measure theflexibility in order to decide on moving the movable gments.The behavior of the over-lap will depend on theflexibility function.If the movable ts over-lap with each other,the maximum offlexibility function can not be obtained by maximizing theflexibility function for each movable t. Therefore dealing with overlaps depends on the definition offlexibility function.We show how to resolve the overlap ifflexibility functions introduced in Section II-D are ud.
Consider moving ts shown in Figure15.In bothfigures,gment overlaps with gment.We will study how the decision on mov-ing the overlapping edges is made by using eachflexibility function mentioned in Section II-D.Note that in the following discussion vari-ables or is ud to define the amount of sliding for the movable gment in movable t.They are not related to coordi-
