# Maximum circular area sum

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.

• In the future you can simply edit the question rather than delete it. Commented Dec 26, 2023 at 13:45
• @tutizeri The sum of all the values in the grid may be smaller than the sum of a circular area within the grid. Imagine if there is exactly one positive number for example.
– Simd
Commented Dec 30, 2023 at 4:39

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.

• The possible radiuses squared are given by OEIS sequence oeis.org/A001481. For square with nodes 0,...,n, there are n=1+n*(n+1)/2 different possible radius. Commented Dec 29, 2023 at 23:51

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.

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)
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.

• The number of relevant radii appears to be linear for coordinates in the middle of the grid and quadratic on the edge. I don't know if this can help.
– Simd
Commented Dec 30, 2023 at 4:33
• I might be wrong that it is linear in the middle but it is definitely much less than at the corner.
– Simd
Commented Dec 30, 2023 at 5:19
• @Simd In the center, you may have 1/4 of the number of relevant radius than at the borders. The number of different radius is O(n^2) (an integral of a triangle), and half of a triangle has 1/4 of the integral. So it changes quadratically with the distance to the farthest border. But that's irrelevant when you use the fast fourier transform, because it does the same calculation on all nodes, almost for free. Commented Dec 30, 2023 at 5:27
• If you use the FFT, you will have to pad it with zeros, otherwise the FFT assume that borders touch, as if they were in a cylinder. But if you use a 2D graphics library, they are already optimized for that, and you will just have to pass a parameter flag to tell it if the data is padded-like or periodic. Commented Dec 30, 2023 at 5:35
• I fixed it. It was an error Commented Dec 30, 2023 at 6:29

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)$$.

• Poly time is a good start!
– Simd
Commented Dec 29, 2023 at 16:05