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

In summary, the conversation discusses an optimization problem involving partitioning a 2D grid with unevenly distributed objects into roughly equal partitions. The problem is not clear and requires further information such as the distribution of objects, constraints on the number of partitions, and secondary objectives. Possible approaches mentioned include starting with a simple algorithm and recursively refining it, or using a graph representation to find an approximate solution.
  • #1
nerdjock
3
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
  • #2
Do you know the distribution of the objects over the grid, in an expectational sense?
 
  • #3
Yes, I know the exact location of all of the objects before I start.

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

1. How do I determine the best layout for my 2D area with objects?

The best layout for a 2D area with objects will depend on the specific goals and constraints of your project. It is important to consider factors such as the size and shape of the area, the type and number of objects, and any specific objectives you are trying to achieve. It may be helpful to use mathematical modeling or simulation techniques to test different layouts and determine the most optimal one.

2. What are some common optimization techniques for 2D area with objects?

Some common techniques for optimizing a 2D area with objects include mathematical optimization algorithms such as linear programming, heuristic methods like genetic algorithms, and machine learning approaches. It is important to carefully evaluate and compare different techniques to determine which one is most suitable for your specific problem.

3. How can I account for changing conditions in my optimization of 2D area with objects?

One way to account for changing conditions is to use a dynamic optimization approach, which continuously adjusts the layout of the objects based on real-time data or changes in the environment. This can involve using predictive models or feedback mechanisms to make adjustments and optimize the area as conditions change.

4. What are some potential challenges in optimizing 2D area with objects?

Some potential challenges in optimizing a 2D area with objects include dealing with complex and dynamic environments, balancing conflicting objectives, and ensuring scalability and efficiency. It is important to carefully consider these challenges and plan accordingly to achieve the best results.

5. How can I measure the success of my optimization for a 2D area with objects?

The success of an optimization for a 2D area with objects can be measured in various ways, depending on your specific goals and objectives. Some common metrics include the total area covered by objects, the number of objects used, and the overall efficiency or cost-effectiveness of the layout. It is important to define clear and measurable goals beforehand to accurately assess the success of your optimization efforts.

Similar threads

Replies
6
Views
945
  • General Math
Replies
8
Views
2K
  • General Math
Replies
33
Views
2K
  • General Math
Replies
2
Views
1K
  • STEM Academic Advising
Replies
2
Views
794
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Differential Equations
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top