Given a rectangle R with area α and a set of n positive reals A = {a_1,a_2,... ,a_n} with ∑_(a_i∈A) a_i =α we consider the problem of dissecting R into n rectangles r_i 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 R, and the maximum aspect ratio ρ(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,1 + max_i=(1,...,n-1) a_i+1/a_i}, where ρ(R) denotes the aspect ratio of R.
展开▼
