• Login
    View Item 
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • Math Prog Technical Reports
    • View Item
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • Math Prog Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Fast Equi-Partitioning of Rectangular Domains using Stripe Decomposition

    Thumbnail
    File(s)
    Fast Equi-Partitioning of Rectangular Domains using Stripe Decomposition (188.0Kb)
    Date
    1996-02-05
    Author
    Martin, Wayne
    Metadata
    Show full item record
    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.
    Permanent Link
    http://digital.library.wisc.edu/1793/65416
    Citation
    96-02
    Part of
    • Math Prog Technical Reports

    Contact Us | Send Feedback
     

     

    Browse

    All of MINDS@UWCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Contact Us | Send Feedback