A Divide and Conquer Approximation Algorithm for Partitioning Rectangles

2023/08/31 by Mohammadi, Reyhaneh, Behroozi, Mehdi
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2308.16899

Abstract

Given a rectangle R with area A and a set of areas L=\A₁,...,A_n\ with ∑_i=1ⁿ A_i = A, we consider the problem of partitioning R into n sub-regions R₁,...,R_n with areas A₁,...,A_n in a way that the total perimeter of all sub-regions is minimized. The goal is to create square-like sub-regions, which are often more desired. We propose an efficient 1.203--approximation algorithm for this problem based on a divide and conquer scheme that runs in O(n²) time. For the special case when the aspect ratios of all rectangles are bounded from above by 3, the approximation factor is 2/√(3) ≤ 1.1548. We also present a modified version of out algorithm as a heuristic that achieves better average and best run times.

Related

• A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
• Smallest k-Enclosing Rectangle Revisited
• On three soft rectangle packing problems with guillotine constraints
• Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation
• Rectangular Partitions of a Rectilinear Polygon