1
$\begingroup$

I have a grid made up of overlapping 3x3 squares like so:

Grid

The numbers on the grid indicate the number of overlapping squares. Given that we know the maximum number of overlapping squares (9 at the middle), and the size of the squares (3x3), is there a simple way to calculate the rest of the number of overlaps?

e.g. I know the maximum number of overlaps is 9 at point (2,2) and the square size is 3x3. So given point (3,2) how can I calculate that there are 6 overlaps at that point?

$\endgroup$
1
$\begingroup$

The maximum number of overlaps is always $k^{2}$ (where $k$ is the small square's side length) (assuming the larger square is always of side length $2k-1$).

The number of overlaps at any other point $(i,j)$ is:

$\min(i,2k-i) \cdot \min(j,2k-j)$

As a pointer towards a proof consider the first row and the first column of the larger square which must always be the sequence $(1,2,\ldots,k,\ldots,2,1)$. Then look at why the other rows and columns are the products of their intersection with the edge row and column.

$\endgroup$
  • $\begingroup$ Sorry - I have just noticed that I've labelled the grid starting from (1,1) instead of (0,0) as in your question. I've left this as it is because it makes the maths slightly simpler. $\endgroup$ – tttppp Sep 16 '10 at 9:46
1
$\begingroup$

If you are just considering $3\times 3$ squares then the number of overlapping squares at the $(i,j)$ is the number of $1\times 1$ squares (including itself) which are internal neighbours. i.e. neighbouring squares which are not on the edge.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.