A [geometric separator](https://en.wikipedia.org/wiki/Geometric_separator) is a line that separates a given set of shapes to two subsets of approximately the same size (up to a constant), while intersecting only a small number of shapes. When a geometric separator exists, it is very useful because it allows us to solve difficult computational geometry problems in a divide-and-conquer manner. 


Example: Given a set of $n$ disjoint axis-parallel squares in the plane, there is a rectangle such that at most $2n/3$ squares are inside it, at most $2n/3$ are outside it, and at most $O(\sqrt{n})$ are intersected by it.


[Smith and Wormald (1998)](http://users.monash.edu.au/~nwormald/papers/geomsep.ps.gz) prove this theorem, as well as thousands of generalizations with various applications. However, there is one generalization I haven't found yet, and I really want to know whether it is true:


**Given $m$ sets, each with $n$ disjoint axis-parallel squares of various sizes, is there a rectangle such that, at most $2mn/3$ squares are inside it, at most $2mn/3$ are outside it, and at most $O(\sqrt{n})$ squares of each collection are intersected by it?**


Note that, because the shapes in each of the $m$ sets are disjoint, the union of all sets is $m$-thick. Therefore, by theorem 39 in the original paper, it is possible to partition the collections such that the *total* number of intersected squares is $O(m\sqrt{n})$. Therefore, when $m=O(1)$, the existence of a simultaneous separator is guaranteed.


On the other hand, when $m \to \infty$, a simultaneous separator may not exist - see the comment by fedja.


The interesting case is when $m=\Omega(\sqrt{n})$. In this case, the existing theorem allows $\Omega(n)$ intersected squares in a single collection. My question is, basically, whether it is possible to bound the number of intersected squares *per collection*.



Simultaneous geometric separator
Expanding fedja's comment, and assuming that the separating rectangle is axis-parallel:


The answer is "no" even if $m=O(n)$, and more generally, whenever $m$ is not bounded.


Let $f:\Bbb N \rightarrow \Bbb N$ be an arbitrary unbounded function.
Let $m\_1 = \frac{99}{100} \cdot f(n)$.
Arrange $n$ unit squares into an $\sqrt{n} \times \sqrt{n}$ grid, forming a square $Q$, and repeat this collection $m\_1$ times.
The boundary of every axis-parallel separating rectangle contains a horizontal or a vertical segment of length $\sqrt{n}/2$ inside $Q$. Tile $Q$ with $nf(n)/400$ squares of side length $20/\sqrt{f(n)}$, and partition them into $m\_2=f(n)/400$ collections, each collection forming roughly an $\sqrt{n} \times 400\sqrt{n}/f(n)$ rectangle. Repeat this tiling once more but rotate the partition by $\pi/2$. In total, we have at most $m\_1 + 2m\_2 < f(n)$ collections, and every separating axis-parallel rectangle intersects some collection in $\sqrt{nf(n)}/20$ squares.


For arbitrarily rotated separating rectangles, the construction can be modified: we tile $Q$ by larger squares, of side length $cf(n)^{-1/4}$, partition the tiling into $O(f(n)^{1/2})$ collections, and repeat this $O(f(n)^{1/2})$ times, each time "rotating" the partition by a small angle of size $O(f(n)^{-1/2})$.


