%A Wayne A. Martin
%T Fast Equi-Partitioning of Rectangular Domains using Stripe Decomposition
%D February 1996
%R 96-02
%I Computer Sciences Department, University of Wisconsin
%C Madison, WI
%X This paper presents a fast algorithm that provides optimal or near optimal
solutions to the minimum perimeter problem. 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 rise to a knapsack integer program that
can be efficiently solved by existing codes. The solution of the knapsack
problem is then used to generate the grid region assignments. An
implementation of the algorithm partitioned a 1000x1000 grid into 1000 regions
to a provably optimal solution in less than one second. With sufficient
memory to hold the MxN grid array, extremely large minimum perimeter problems
can be solved easily.