Fast Equi-Partitioning of Rectangular Domains using Stripe Decomposition

Abstract

This paper presents a fast algorithm that provides optimal or near optimal solutions to the minimum perimeter problem on a rectangular grid. The minimum perimeter problem is to partition a grid of size MxN into P equal area regions while minimizing the total perimeter of the regions. The approach taken here is to divide the grid into stripes that can be filled completely with an integer number of regions. This striping method gives size to a knapsack integer program that can be efficiently solved by existing codes. The solution of the knapsack algorithm partitioned a 1000x1000 grid into 1000 regions to a provably optimal solution in minimum perimeter problems can be solved easily.