Legend
Legend

Reputation: 116950

Better way to solve this grid-search problem?

I have a grid (not necessarily a square but I drew it as a square to simplify it) and certain values associated with each of the smaller squares. Given a circle of radius x, I am trying to find the region where the sum of the values is the maximum. The following picture will make it clear:

enter image description here

My guess here is that if a plane is divided into a grid using a large number of small squares, approximating the circle to a square will only lead in some over-approximation which is ok to me initially because I have not yet finalized how to address the case of a circle overlapping with a partial square (what would its value be?).

The simplest approach I can think of is brute-force: Start perhaps at the lower left and start moving in a zig-zag path until we hit the top-right and output the region with the maximum sum. I am fine with this approach but for large plane regions, there will be huge number of squares and at some might this approach might prove expensive. I am not sure if there is a better way of solving this problem but I would really appreciate if anyone had other thoughts on how to go about solving this.

Upvotes: 4

Views: 1462

Answers (4)

The rectangle-case and the circle case are quite different.

If you are looking for the best rectangular-region, your brute-force approach is O(nk) (n=total number of tiles, k=number of tiles inside a the region), which can easily be improved to O(n) by caching some partial-sums along the rows/columns - this is the best you can possibly do, since you must look at every tile at least once. If you need to do this often, with a changing region or tiles, a spacial data-structure would be faster than O(n), at the cost of some initial setup.

For the circle case, if the circle's center is restricted to tile-edges, I'm not sure how you would improve on your O(nk) brute-force algorithm.

However, if the circle can truly be anywhere like you stated, you cannot naievly brute-force every possible circle-position, because there are infinite possible positions!

Instead, you need something a bit more clever; see for example this answer (consider the center of each tile as a weighted-point). Note that, since the points are weighted, you must keep in mind that it is possible for the best circle to have only one point!

Upvotes: 1

Jose M Vidal
Jose M Vidal

Reputation: 9160

I have an idea that might help speed up the search for the case where the size of the circle is much larger than that of the little squares.

Instead of moving the circle one small square at a time you start by tiling the whole plane with non-overlapping circles and calculating the value for each one of these. This will let you establish upper bounds on the possible sums of all remaining circles.

For example, say you have just nine circles, in a 3x3 tiling of the plan, and their sums are:

10 10 10
10  1  1
1   1  1

Then you know that the most that any circle could have is 31, and a circle of 31 would have to overlap the 4 circles on the top-left: 0,0 0,1 1,0 and 1,1 (row,col positions from top left).

Given the numbers above you can immediately ignore all circles that lie solely within the bottom-right area: 1,1 1,2, 2,1 2,2.

Implementing this algorithm will be a bit tricky, but it should work and give you tons of speedup, if the circles are much bigger than the squares and the numbers are unevenly distributed (that is, if some areas tend to have bigger numbers than others).

Upvotes: 0

CygnusX1
CygnusX1

Reputation: 21818

For finding a sum in a rectangle in a regular grid, there is actually a simple algorithm for doing that in O(n). Let G be that grid and g(x,y) is the value at cell (x,y)

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

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

I understand that your original problem is more complicated than that, but maybe similar approach can be adopted?

Upvotes: 1

JAB
JAB

Reputation: 21089

Unless there are trends to the data in the smaller squares, I think a brute-force approach might indeed be required for that, though you might want to figure out one that wouldn't take the polynomial or exponential time that I believe a naive brute-force approach would require.

However, if there are trends (things like higher values tend to be grouped together, or you're more likely to encounter higher values on one side than on another), you could set up an algorithm that would predict regions of your grid that are more likely to contain the higher values.

I might be missing something, of course.

Upvotes: 1

Related Questions