Best way to solve this grid problem?

Question

I have a grid (not necessarily a square, but I painted it as a square to simplify it) and some values ​​associated with each of the smaller squares. Given a circle of radius x , I am trying to find the area where the sum of the values ​​is maximum. The following figure will be clear:

My assumption is that if the plane is divided into a grid using a large number of small squares, approximating the circle to the square will only lead to some redefinition, which is fine for me, because I have not yet finalized how to address the case of a circle overlapping with a partial square (what would be its significance?).

The simplest approach I can come up with is brute force. Perhaps start in the lower left corner and start moving along a zigzag path until we reach the upper right and bring out the area with the maximum amount. I am fine with this approach, but for large flat regions there will be a huge number of squares, and perhaps this approach can be expensive. I am not sure if there is a better way to solve this problem, but I would really appreciate it if someone had other thoughts on how to solve this problem.

Answer 1

If there are no data trends in the smaller squares, I think that this may require a brute force approach, although you may need to figure out one that will not take polynomial or exponential time, which I think a naive brute force approach will require.

However, if there are trends (things like higher values ​​are usually grouped together, or you are more likely to come across higher values ​​on the one hand than the other), you can set up an algorithm that will predict the regions of your grid which are more likely to contain higher values.

I might have missed something.

Answer 2

The case of the rectangle and the round circle are very different.

If you are looking for the best rectangular area, your brute force approach O(nk) (n = total number of tiles, k = number of tiles within a region) that can easily be improved to O(n) by caching partial sums along rows / columns is the best that you can do, since you must look at each plate at least once. If you need to do this often, with changing regions or tiles, the spatial data structure will be faster than O (n), due to some initial configuration.

For the case of a circle, if the center of the circle is bounded by the edges of the tile, I'm not sure how you will improve your brute force algorithm O(nk) .

However, if the circle can really be anywhere, as you said, you cannot naively go through all possible round positions, because there are infinite possible positions!

Instead, you need something smarter; see, for example, this answer (consider the center of each tile as a weighted point). Note that since the points are weighted, you should keep in mind that the best circle can only have one point!

Answer 3

To find the sum in a rectangle in a regular grid, there really is a simple algorithm to execute in O (n). Let G be the grid and g (x, y) the value in the cell (x, y)

Let H be a new mesh such that h (x, y) = sum g (i, j) for all i <= x; j <= y (you can do this in linear time).

Now the sum in the rectangle (x1, y1) .. (x2, y2) is equal to h (x2, y2) -h (x1, y2) -h (x2, y1) + h (x1, y1).

I understand that your initial problem is more complicated, but maybe a similar approach can be taken?

Answer 4

I have an idea that could speed up the search for a case where the size of the circle is much larger than the size of small squares.

Instead of moving the circle one small square at a time, when you start by breaking the entire plane into disjoint circles and calculating the values ​​for each of them. This will allow you to set the upper bounds on the possible sums of all other circles.

For example, let's say that you have only nine laps in a 3x3 tiling plan, and their total:

 10 10 10 10 1 1 1 1 1 

Then you know that the greatest that any circle can have is 31, and a circle of 31 should overlap 4 circles in the upper left corner: 0.0 0.1 1.0 and 1.1 (line, position col top left).

Given the numbers above, you can immediately ignore all circles that lie exclusively in the lower right area: 1.1 1.2, 2.1 2.2.

The implementation of this algorithm will be a bit complicated, but it should work and give you a ton of acceleration if the circles are much larger than the squares and the numbers are unevenly distributed (that is, if in some areas there are more numbers than others).