4

We consider the following problem: given a set of $N$ squares in the plan, what is the maximum number of ways they can overlap ?

Rules of construction:

  1. Two arrangements of squares are considered the same if one can be continuously changed to the other without any vertex passing through an edge.
  2. The squares can be re-scaled, rotated and translated but they must keep their square shape. They must be contained in a finite space and cannot be reduced to a point.
  3. A vertex cannot be superimposed with an edge or with another vertex.
  4. Turning the whole configuration over is allowed (mirror image) and doesn’t change the arrangement.
  5. The squares are drawn in an affine plane.

Surprisingly I didn’t find anything about this in the literature but maybe I didn't search well...

I tried to establish an isomorphism between the geometric objects and their algebraic representations in order to count them. Anytime I generate an arrangements (with a brute force algorithm) I calculate its algebraic representations and check if it's a new one.

Basically my method (For N=3) is to calculate 3 matrices:

  1. $V(i, j)$ = number of vertices from the square i included in the square j
  2. $F(i, j)$ = number of intersections found on the edge j of the square i
  3. $S(i, j)$ = index of the sub-polygon (in the arrangement formed by the 2 other squares) in which the vertex j of square i is included*

*The third matrix takes into account the sub-polygons created by the overlapping squares and a certain number of symmetry criterias in order to avoid counting the same arrangement several time.

I didn’t prove yet that my model create an isomorphic (for N=3) but I'm pretty sure it can be use to calculate a good lower bound.

So far I found $12$ arrangements for $N=2$ (visible below) and more than $4600$ for $N=3$. But I cannot make my algorithm converge for $N=3$ because I’m limited by the capacity of my computer...

Arrangements found for N=2

enter image description here

Questions: Has this problem been already solved? Is it possible to find a formula expressing explicitly the number of arrangements possible for any value of $N$?

Félix Debon
  • 41
  • For $N=2$ I only find $4$ configurations, assuming indiscernible vertices (otherwise there are many more). Can you show yours ? –  Nov 07 '19 at 10:05
  • @YvesDaoust I initially got stuck at $4$ configurations, but many more become apparent when you rotate one of the squares. I too would like to see images of the $N=2$ configurations. – nickgard Nov 07 '19 at 10:36
  • I think I've worked out all 12. I'll use $(a,b)$ to mean that $a$ vertices of the first square lie inside the second, and $b$ vertices of the second lie inside the first. There are two $(0,0)$ arrangements (disjoint, or octagonal star), three $(1,0)$ depending on whether the "inner" square intersects 1, 2, or 3 sides of the other, two $(2,0)$, one $(3,0)$, one $(4,0)$, two $(1,1)$, and finally one $(2,1)$. – Jaap Scherphuis Nov 07 '19 at 10:46
  • 3
    I just added an image with the arrangements found for $N = 2$ – Félix Debon Nov 07 '19 at 10:50

0 Answers0