05-07-2012, 01:00 PM
An Optimal Algorithm for Finding Disjoint Rectangles and Its Application to PCB Routing
An Optimal Algorithm.pptx (Size: 509.34 KB / Downloads: 24)
Introduction
The maximum disjoint subset (MDS) of a group of rectangles is defined to be a subset of non-overlapping rectangles with the maximum total weight.
The general MDS problem, which is finding the MDS of general rectangles, has been proven to be NP-complete.
The problem of finding the MDS of a set of boundary rectangles remains open and is closely related to some difficult routing problems in PCB design.
Given a rectangular region R, a rectangle r lying within R is said to be a boundary rectangle if r has at least one boundary attached to the boundary of the rectangular region R.
Problem formulation
Given a rectangular region R and a set S of boundary rectangles {1, 2, . . . , n} lying within R, where each boundary rectangle i is associated with a weight wi, the MDS problem of S is to find a subset of S such that chosen boundary rectangles do not overlap with each other while their total weight is maximized.
Algorithm
We use M® to represent the set of boundary rectangles in the optimal solution, and we use w(M®) to denote the total weight of its rectangles.
We divide all the boundary rectangles in S into four subsets according to their specified attaching boundaries, namely, Sl, Sr, St and Sb, and they correspond to the subsets whose boundary rectangles’ attaching boundaries are, respectively, the left, right, top and bottom boundaries of the rectangular region R.
Thus we have Sl ∪Sr ∪St ∪Sb = S.
The most general case of the MDS problem is that all four subsets Sl, Sr, St and Sb are nonempty, and we call it the 4-boundary case.
There are several special or degenerate cases of the MDS problem, where some of the subsets Sl, Sr, St and Sb is(are) empty.
Thus we also have 1-boundary, 2-boundary and 3-boundary cases.
The 2-boundary case can be subdivided into two cases: the corner case (e.g., Sl and Sb are nonempty) and the opposite case (e.g., Sl and Sr are nonempty).
The Corner 2-Boundary Case
For ease of presentation, here we only discuss the bottom-left corner case(St and Sr are empty).
Flow
Construct a Hanan grid of on the rectangular region.
construct a direct acyclic graph (DAG) based on the Hanan grid.
The longest path from bottom-left point to top-right point on the constructed DAG equals the total weight of the boundary rectangles in the optimal solution.
Conclusion
In this paper, we proposed a polynomial time algorithm to optimally solve an open problem, the maximum disjoint subset problem of boundary rectangles.
We then showed that this algorithm can be applied to find the optimal solution of the bus escape routing problem.