Given weighted points on a plane, find locations for U squares such that the total enclosed weight would be maximized

Question

I'm faced with the following problem:

Given

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

Goal:

• Assign (find locations for) the squares such that the total points' weight enclosed within all the squares would be maximized.

Notes:

• The squares should be axis-parallel
• The squares may overlap, but the enclosed weights won't be counted more than once.

I'm looking for an optimal assignment.

My questions:

• Is this a known problem (Does it has a name? Has it been explored before?).
• Any ideas how to approach it?

(I may be expected to mention what have I tried. Since I'm looking for an optimal assignment, my heuristic ideas are not really relevant. At this point I have no idea how to find the optimal assignment).

Answer 1

It's a geometric special case of the weighted maximum coverage problem. The general MCP is NP-hard, and I suspect that this special case is as well, though unlike the general case, it probably has an efficient polynomial-time approximation scheme. You want an optimal solution, however, so the first thing that I would recommend is to feed the integer linear programming formulation in the linked Wikipedia article to 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 weight w_j of each point j is given, and the sets S_i are all possibilities for covering points with a width L square. The meaning of x_i is whether set S_i is chosen. The meaning of y_j is whether point j is covered. The simplest cubic algorithm for constructing the S_is is to enumerate all squares whose lower left vertex has x coordinate equal to that of some point and y coordinate equal to that of some (possibly other) point, since every other square can be slid up and/or to the right without sacrificing coverage.