Optimizing 2D Area with Objects - CS Graduate Student Seeking Advice

  • Context: Graduate 
  • Thread starter Thread starter nerdjock
  • Start date Start date
  • Tags Tags
    Area Optimization
Click For Summary

Discussion Overview

The discussion revolves around an optimization problem related to partitioning a 2D grid of cells containing objects. The goal is to create P contiguous partitions that each contain roughly the same number of objects. The conversation explores techniques and considerations for solving this problem, including algorithmic approaches and constraints.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • The original poster seeks guidance on optimization techniques suitable for partitioning a 2D grid with unevenly distributed objects.
  • One participant inquires about the distribution of objects in an expectational sense, suggesting a need for understanding the overall layout.
  • The original poster clarifies that they know the exact locations of all objects prior to partitioning.
  • Another participant proposes starting with a binary partitioning approach, recursively adjusting partitions to balance the number of objects, while questioning the specific optimization goals.
  • This participant raises several questions regarding constraints, such as the allowable range of objects in each partition, the number of partitions, and whether partition sizes should be equal in terms of cell counts.
  • Additionally, an alternative approach is suggested involving the creation of a network graph based on object locations, with a method for refining connections to achieve the desired partitions.

Areas of Agreement / Disagreement

Participants express varying perspectives on the optimization techniques and constraints involved, indicating that there is no consensus on a single approach or solution at this time.

Contextual Notes

Participants highlight several assumptions and constraints that may affect the optimization process, including the distribution of objects, the number of partitions, and the computational efficiency based on the size of the grid and number of objects.

nerdjock
Messages
3
Reaction score
0
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!
 
Mathematics news on Phys.org
Do you know the distribution of the objects over the grid, in an expectational sense?
 
Yes, I know the exact location of all of the objects before I start.

Thanks,
Mike
 
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.
 

Similar threads

Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Statistical physics in 2D world: How to simulate gas and its interaction with objects? (game design)
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Dimensional Consistency in Grid Defintions
  • · Replies 8 ·
Replies
8
Views
2K
Automotive Topology optimization of an engine's cylinder block
  • · Replies 14 ·
Replies
14
Views
2K
High School Self-descriptive Physical Object
  • · Replies 33 ·
2
Replies
33
Views
3K
Admissions Sincerely seeking graduate school admission advice
  • · Replies 20 ·
Replies
20
Views
3K
WaveGrid - Non-equilibrium Emergence Sandbox
  • · Replies 1 ·
Replies
1
Views
3K
Placing a pole with maximal radius subject to constraints
  • · Replies 3 ·
Replies
3
Views
1K
Courses How much Chemistry should I take to prepare for Biophysics PhD?
  • · Replies 2 ·
Replies
2
Views
2K
Admissions Graduating a year early anxieties + grad school
  • · Replies 15 ·
Replies
15
Views
2K