Given the weighted points on the plane, find the locations for the U-squares so that the total closed weight will be maximized

Question

I ran into the following problem:

Considering

• The set of points on the Euclidean plane, each point P (x, y, w) has coordinates and an associated positive weight.
• A set of squares U having the same size L.

Purpose:

• Assign (find places for) the squares so that the total weight of the points enclosed within all the squares is maximized.

Notes:

• Squares must be parallel to the axis
• Squares may overlap, but applied weights will not be counted more than once.

I am looking for the best destination.

My questions:

• This is a known issue (does it have a name? Has it been studied before?).
• Any ideas how to approach it?

(Perhaps I should mention that I tried. Since I am looking for the optimal destination, my heuristic ideas are not very relevant. At the moment, I have no idea how to find the optimal destination).

Answer 1

This is a geometric special case of a weighted maximum coverage problem . The general MCP is NP-hard, and I suspect that this particular case is also, although unlike the general case, it probably has an effective polynomial time approximation scheme. However, you want an optimal solution, so the first thing I would recommend is to combine the integer formulation of linear programming in a related Wikipedia article with an LP solver.

maximize sum_j (w_j * y_j) subject to for all i, sum_i x_i <= U for all j, sum_{i : j in S_i} x_i - y_j >= 0 for all i, x_i in {0, 1} for all j, 0 <= y_j <= 1 

The mass w_j each point j , and the sets S_i are all the possibilities for covering points with a square of width L The value of x_i is whether the set S_i selected. The value of y_j is whether point j covered. The simplest cubic algorithm for constructing S_i is to list all the squares whose lower left vertex has an x ​​coordinate equal to the coordinate of some point and y equal to the coordinate of some (possibly another) point, since each other square can be moved up and / or to the right without sacrificing insurance.