A friend told me a problem that he had been trying to optimize for a personal graphics project, and it involved having an h × w grid, and wanting to do some pre-processing to answer circle-sum queries. A circle here would be defined as having some center, (yc, xc), where 1 ≤ yc ≤ h and 1 ≤ xc ≤ w and some radius r, and it is the set of integer grid points (y, x) such that (x - xc)2 + (y - yc)2 ≤ r2.
The progress he's made is that in O((hw)2) pre-processing, you can just precompute all the possible queries, so one possible set of complexities is O((hw)2) pre-processing and O(1) queries. Another possibility is to precompute prefix sums in O(hw) time and answer the queries in O(r) time.
Is there any clever way to get a better set of pre-processing and query complexity than the two methods mentioned above?
