0

Given M polygons each with weight w_i, write a fast algorithm that outputs N polygons such that:
- no two polygons intersect
- \sum w_i is maximized

Are there any optimizations possible when the input polygons are axis aligned rectangles? non axis aligned rectangles?

Adding some references:
1. Label Placement by Maximum Independent Set in Rectangles
2. Maximum Independent Set of Rectangles
3. Finding maximum non-overlapping intervals in 1 dimension

Community
  • 1
  • 1
morpheus
  • 18,676
  • 24
  • 96
  • 159
  • Since you are tying to maximize the sum. You might be better of trying to separate all of the rectangles into some number of independence sets (via a greedy algorithm), then try to merge them together to see what intersections are caused. This may be benefital since the goal is to make a high valued independent set. – Nuclearman Mar 19 '14 at 20:23

2 Answers2

2

You can approach this problem as a graph one. The graph nodes are your polygons, the graph edges mean "no intersection" - then your problem becomes the Maximal Clique Problem. Please see the general discussion about cliques in graphs here. You can search for "maximal-weight clique algorithms" as well.

Talking about a practical approach - you can try the Boost Graph Library, it contains algorithms to list all cliques in a graph.

Of course, this approach requires you to calculate all the pair-wise intersections in advance. So, the problem is being reduced to another one - given a set of polygons, find a fast way to calculate a "non-intersecting" matrix. I think, this one can be solved by plane sweeping.

HEKTO
  • 3,876
  • 2
  • 24
  • 45
0

Assuming positive weights, only maximal subsets of nonintersecting polygons are to be considered (if you remove an element from a maximal subset, the sum decreases).

You could try an incremental approach: assume that for the M first polygons, you have found all maximal subsets of nonintersecting polygons. Take into account one more polygon. You will form new maximal nonintersecting subsets by considering all available subsets and discarding from them all the polygons that intersect the new one.

Example: A, B, C, D. A and B intersect, A and C intersect.

Start from { A }.

Add B. Form { A, A U B }. Discard A from A U B. You keep { A, B }.

Add C. Form { A, B, A U C, B U C }. Discard A from A U C and absorb B in B U C. You keep { A, B U C }.

Add D. Form { A, B U C, A U D, B U C U D }. You absorb B U C in B U C U D and keep { A U D, B U C U D }.

The solution is the maximal subset with the largest sum.

It is probably better to precompute the intersections by exhaustive search (O(N^2) intersection computations), or by more efficient approaches (possibly down to O(N.Lg(N) + K) intersection computations).

But the construction of the subsets might be exponential in the number of polygons :( I don't know.

It is also possible that a dynamic approach will allow you to get rid of certain subsets earlier (processing the polygons in a certain order such as by increasing or decreasing number of intersections ?).

  • You're neglecting that the goal is find the independence set with maximum value. Although, that largely just changes the order in which to check subsets. – Nuclearman Mar 19 '14 at 20:18
  • Not at all. I said 1) Assuming positive weights, only maximal subsets of nonintersecting polygons are to be considered. 2) The solution is the maximal subset with the largest sum. 3) It is also possible that a dynamic approach will allow you to get rid of certain subsets earlier... –  Mar 20 '14 at 01:00