Kognition's blog

By Kognition, history, 6 years ago, In English

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?

  • Vote: I like it
  • +34
  • Vote: I do not like it