Show simple item record

dc.contributor.authorMartin, Wayne
dc.description.abstractThis 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.en
dc.titleFast Equi-Partitioning of Rectangular Domains using Stripe Decompositionen
dc.typeTechnical Reporten

Files in this item


This item appears in the following Collection(s)

  • Math Prog Technical Reports
    Math Prog Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record