An approximation algorithm for dissecting a rectangle into rectangles with specified areas

Given a rectangle R   with area αα and a set of n   positive reals A={a1,a2,…,an}A={a1,a2,…,an} with ∑ai∈Aai=α∑ai∈Aai=α, we consider the problem of dissecting R into n   rectangles riri with area ai(i=1,2,…,n) so that the set RR of resulting rectangles minimizes an objective function such as the sum of the perimeters of the rectangles in RR, the maximum perimeter of the rectangles in RR, and the maximum aspect ratio of the rectangles in RR, where we call the problems with these objective functions PERI-SUM, PERI-MAX and ASPECT-RATIO, respectively. We propose an O(nlogn)O(nlogn) time algorithm that finds a dissection RR of R   that is a 1.25-approximate solution to PERI-SUM, a 23-approximate solution to PERI-MAX, and has an aspect ratio at most max{ρ(R),3,1+maxi=1,…,n-1ai+1ai}, where ρ(R)ρ(R) denotes the aspect ratio of R.