# Algorithmic challenge: generate a list of random non overlapping squares

For an undisclosed reason, I need a list of $$n$$ squares in a two dimensions space where each square does not overlap.

So the challenge is simply: given a two dimensional area $$a$$ (topLeft: int, topRight: int, width: int, height:int), a number of squares required $$n$$ and a size for each square $$s$$: generate a list $$L$$ of $$|L|=n$$ squares in $$a$$ where the following condition holds. $$\forall q,r \in L , q \neq r \implies \textrm{no_overlap}(q,r) \land \textrm{inside}(q,a)$$ where no_overlap is a function that checks if square $$q$$ and $$r$$ do not overlap given the size $$s$$ and inside(q,a) checks if square $$q$$ is completely inside the area $$a$$.

I tried coming up with a solution myself but the only thing I can find is to brute force generating a square, check if there is overlap and if not ,add it to $$L$$. But as one might see, this algorithm could theoretically run forever. I would need something which is guaranteed to work in a finite time and preferably be of a complexity of at most $$\mathcal{O}(n^2)$$. So I thought to myself, maybe I could share this with other people around the world and see what clever ideas they have in mind. I most certainly find it an interesing theoretical question to ask. The practical reason is for a Unity 3D (game) project I am making.

EDIT: This would be a possible solution graphically illustrated for $$n=7$$

• (Doesn't this look $height*width$ choose $n$?) Dec 25 '20 at 18:35
• Why can't you just generate squares $(0,0,s,s)$, $(0, s, s, 2s)$, $\ldots$, $(0, ks, s, (k+1) s)$, $(s, 0, 2s, s)$, $(s, s, 2s, 2s)$, $\ldots$.
– user114966
Dec 25 '20 at 19:04
• Are we allowed to rotate the squares inside the area $a$? So that we can efficiently use the space... Dec 25 '20 at 20:22
• Assuming $s$ integral too, I thought rotation doesn't me anywhere. But there are square numbers that are sums of two squares and three orientations for rectangles that size. Dec 26 '20 at 8:58
• @Inuyashayagami yes the rotation of the squares is of no concern Dec 26 '20 at 10:31

You could perhaps use a 2 dimensional k-d tree to store the set of free positions $$(x, y)$$ where the left upper corner of a new square could be chosen without overlapping the existing squares. Each node of the tree covers a region in the area $$a$$ and you can decorate this node with this region's coordinate and the number of free positions that it contains. At the top of the tree, you can read the total number of available slots and simply choose a random number to get the index of that slot. By walking downwards in the tree, you can find which slot corresponds to this random number, then update the tree accordingly to add a new square.
My intuition is that the amount of data contained in the tree is approximately proportional to the number $$k$$ of squares already chosen and that the addition of a new square should be proportional to $$\log k$$ on average.
Edit: I wrote a working implementation in python 3 by using a tree structure. I'm not sure about the performance for large $$n$$ but it could already be measured experimentally. I didn't make any effort to balance the tree but as new squares are chosen randomly, this randomness should balance the tree on average.
• Interesting theory, but $a$ is continious so there could actually be infinite free spaces but you answer would be an acutal solution to my practical problem Dec 27 '20 at 14:07