Given a rectangle R with area α and a set of 71 positive reals A = {a_1,a_2,…,a_n} with Σ_(ai∈A) ai = α, we consider the problem of dissecting R into n rectangles r_n with area a_i, (i = 1,2,…,n) so that the set R of resulting rectangles minimizes an objective function such as the sum of perimeters of the rectangles in "R., the maximum perimeter of the rectangles in 1Z, and the maximum aspect ratio p(r) of the rectangles r ∈R, where we call the problems with these objective functions PERI-SUM, PERI-MAX and ASPECT-RATIO, respectively. We propose an O(n log n) time algorithm that finds a dissection R of R that is a 1.25-approximation solution to the PERI-SUM, a 2/3~(1/2)-approximation solution to the PERI-MAX, and has an aspect ratio at most max{ρ(R), 3,l + max_(i=1,…,n-1)}, where ρ(R) denotes the aspect ratio of R.
展开▼
