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

AbstractGiven a rectangle R with area α and a set of n positive reals A={a1,a2,…,an} with ∑ai∈Aai=α, we consider the problem of dissecting R into n rectangles ri with area ai(i=1,2,…,n) so that the set R of resulting rectangles minimizes an objective function such as the sum of the perimeters of the rectangles in R, the maximum perimeter of the rectangles in R, and the maximum aspect ratio of the rectangles in R, where we call the problems with these objective functions PERI-SUM, PERI-MAX and ASPECT-RATIO, respectively. We propose an O(nlogn) time algorithm that finds a dissection R 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) denotes the aspect ratio of R