CODEWITHSUNDEEP
algorithm
Mayan
Mayan

Reputation: 492

Algorithm searching for the largest area formed by non overlapping rectangles

Given some rectangles on a 2D coordinate plane, I want to find an algorithm to find the largest area formed by non overlapping rectangles.

My first thought was:

  1. Check whether rectangle Ri, Rj overlap for all i,j

  2. Rectangle Ri is a node. We construct an edge between any pair of rectangle Ri, Rj which are not overlapping

  3. We then have an undirected graph

  4. Find all sub graphes which are complete graphs.

  5. Sum the weight of the nodes and find the largest one

However, this brute force way is NP complete already. I don’t see a simple greedy algorithm which works either. I wonder if there is any polynomial time method to solve the problem. Thanks!

Upvotes: 4

Views: 322

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

Integer programming would be a good fit for this problem. Using a solver library, set up the following integer program.

maximize sum_{rectangles R} area(R) x_R
subject to
for each pair of overlapping rectangles R1, R2:
    x_R1 + x_R2 <= 1
variables x_R in {0, 1} for each rectangle R

The interpretation of the variables is that x_R = 1 if rectangle R is included in the optimal set.

If your solver is smart and adds clique cuts during its presolve, then this formulation is fine. Otherwise, you should detect maximal cliques in the overlap graph (nodes are rectangles, edges are overlapping rectangles) and write a constraint that at most one rectangle in each clique is present. (If this step is too slow, you might also use a sweep-line algorithm to find maximal sets of overlapping rectangles.)

Upvotes: 1

Related Questions