Maximum circular area sum

Question

Given an $n \times n$ grid of integers, I would like to compute the circular area which gives the maximum sum of integers within the area. For example:

In this picture, the integers 1, 0, 1, 2, 3, 1, 2, 1, -3, -2, 2, -3, 1, 3, -2, 0, 2, -1 etc are all within the circular area.

If we restrict the circular area to be centered at one of the grid points, is there an efficient algorithm for this problem?

The input is just the grid of integers. The task is to find the center and radius. If the circular area includes part outside the grid that part contributes zero to the sum.

Answer 1

There are $n^4$ possible $(x, y, r^2)$ tuple, each describing a circle centered at $(x, y)$ with radius $r$. Since each circle is its smaller version added with $O(1)$ additional points, this yields a time complexity of $O(n^4)$. We may find the additional points by sorting every $r^2 = a^2 + b^2$ pair.

Answer 2

The possible radiuses squared are given by OEIS sequence A001481.

For square with nodes $0,...,n$, there are $1+(n+1)(n+2)/2$ different possible radius. (but only $1+n(n+1)/2$ are inside the rectangle).
You better work with the radius squared, since is integer arithmetic, which is faster than float.

This quadratic equation is the number of nodes inside half a quadrant of a circle. (It double counts a small number of nodes, but is roughly correct).

If you displace this circle to the center, the base of the triangle is reduced th 1/2, which reduces the node count to 1/4 (think of the large triangle as made out of 4 small triangles).

for $0$ to $9$, you get $67$ different radius to try. The radius squared are

0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29, 32, 34, 36, 37, 40, 41, 45, 49, 50, 52, 53, 58, 61, 64, 65, 68, 72, 73, 74, 80, 81, 82, 85, 89, 90, 97, 98, 100, 101, 104, 106, 109, 113, 116, 117, 121, 122, 125, 128, 130, 136, 137, 144, 145, 146, 148, 149, 153, 157, 160, 162

Note that you only need to calculate those radius in 1/8 of the 360º, because the rest of the circle is symmetrical, and do not add more unique radius.

Adding the nodes, for each radius, is a 2D convolution.

First you make a circular mask, for each radius, and then use the mask to calculate the convolution on all nodes (most algorithms use the fast fourier transform).
The mask has $1$ for all the nodes where $\Delta x^2+\Delta y^2 \leq r^2$, and has $0$ on the nodes outside the circle.
Any graphic library has already coded optimized functions to calculate 2D convolutions,and maybe even to create a circular mask.

for each unique radius -> O(n^2)
    create mask -> O(n) since you only need to add periferic nodes to the smaller mask.
    calculate convolution -> O(n^2)log(n) size
    find max value in the convolution -> O(n^2)

It is a brute force $O(n^4\log(n))$ algorithm, but the convolution is relatively cheap, and probably may be reused with larger masks.

Answer 3

I'm not sure if the algorithm qualifies as "efficient", but at least it works in polynomial time. The idea is that for a given pair pair $(x,y)$ of coordinates, there is at most $n^2$ many radiuses to consider (indeed, two discs that contain exactly the same points will have the same sum).

To enumerate these discs, start with radius $r=0$. Then following procedures takes a radius $r \geq 0$ (not necessarily a natural number!), and returns the smallest radius $r' \geq 0$ such that the disc centered at $(x,y)$ of radius $r'$ contains strictly more points than the disc of radius $r$: it suffices to compute all points $(x',y')$ that do not belong to the disc of radius $r$, and pick any point with minimal distance to $(x,y)$. Return the distance from $(x',y')$ to $(x,y)$.

Overall this gives you a polynomial time procedure to enumerate all sets of points contained is a disc centered at $(x,y)$. Then it suffices to iterate this over all coordinates $(x,y)$.