Optimization of Area

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!

EnumaElish

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

nerdjock

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

Thanks,
Mike

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?
Questions I would ask:
Is there a range in the number of objects allowed in each partition?
Are there constraints on the number of partitions?
Is there a secondary quantity to be optimized, e.g. do you want partition sizes in terms of cell counts to be roughly equal or as equal as possible?
Are there a very large number of either cells or of objects which would affect which approach is computationally quicker?


Another approach which comes to mind is to work with an initial network (graph) connecting all the objects (using cell positions as coordinates?) Then trim connections starting from longest to shortest which cross other connections. Also treat multiple objects in a single cell as a single node on the graph. Then the dual of this graph should be close to the partition you are trying to find.