# Optimization of Area

1. Jul 4, 2009

### nerdjock

Hello,

I am a CS graduate student, and I have a curious optimization problem which i need to solve, and have no idea where I should be looking for techniques for solving it. I have searched much material on optimization techniques, but still am not sure which subject this falls under. I would really appreciate if someone could even point me in the right direction as to what material I should be looking at to solve this.

Allow me to explain the problem. I have a regular 2D grid of cells. Each of these cells can contain "objects" of interest. The objects are not necessarily distributed evenly throughout the grid, and often are not. I need to partition the grid into P partitions, such that each partition will contain roughly the same number of "objects". Each partition can contain a different number of grid cells, with the constraint that each partition is made up of a contiguous region of cells (i.e. the paritions cannot be a disjoint collections of grid cells).

Forgive me if I am posting in the wrong forum, as I was not sure where to post this at all! :P

Any help is much appreciated.
Thanks!

2. Jul 4, 2009

### EnumaElish

Do you know the distribution of the objects over the grid, in an expectational sense?

3. Jul 4, 2009

### nerdjock

Yes, I know the exact location of all of the objects before I start.

Thanks,
Mike

4. Jul 4, 2009

### jambaugh

If it were me I would start with an algorithm which partitions the grid into two halves, then counts objects in each half and varies the partition until both halve have roughly equal numbers. Then apply recursively with each half grid.

I'm not clear on exactly what it is you want to optimize?