On the Optimal Decomposition of Rectangular Domains
Ioannis Christou
Department of Computer Sciences
University of Wisconsin-Madison
christou@cs.wisc.edu
2:30 pm Fri. Nov. 18 in 2310 Computer Sciences and Statistics Bldg.
In this talk, I shall present an efficient method for the partitioning of
rectangular domains into equi-area sub-domains of minimum total perimeter, a
problem of intrinsic beauty with applications in scientific computing. This
method is based on utilizing, to the maximum extent possible, a set of optimal
shapes for sub-domains. PERIX-GA, a genetic algorithm employing this approach,
has succesfully solved million-variable instances of the perimeter
minimization problem. The results of an implementation on a CM-5 multiprocessor
will be presented as well as error bounds from a computable lower bound.