# Simultaneous geometric separator

A 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) 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.

• About the squares in your question: are they all assumed to be congruent? Parallel translates of one? Homothetic copies of one? Arbitrary sizes and orientations? Also, I guess the squares in one set need not be disjoint from the squares in another, right? – Wlodek Kuperberg Jan 14 '14 at 13:33
• The squares are axis-parallel but can be of any size. The squares in every set are disjoint, but the squares in different sets may intersect. – Erel Segal-Halevi Jan 14 '14 at 17:04
• Must the rectangle be axis-parallel too? – James Cranch Jan 20 '14 at 0:37
• No. Take one collection of $n$ squares and repeat it an enormous amount $M$ of times. Then any separator of this collection has to have a noticeable size line segment within some fixed compact area. Now for each such line segment draw $n$ squares on that segment and notice that each such set of $n$ squares spoils some neighborhood of that segment as well. So, a finite number $m$ of additions is enough to spoil all such segments and this number does not depend on the number of repetitions, so we can keep $m$ bounded as $M\to\infty$ – fedja Jan 20 '14 at 3:48
• @Erel I assume that you are referring to their Theorem 39; they remark that in the plane, the number of intersected squares in at most $4\sqrt{\kappa N}$, where $N=mn$ and $\kappa=m$, so $\sqrt{\kappa N}=m\sqrt{n}$. Of course for $m=O(1)$ this is $O(\sqrt{n})$. – Jan Kyncl Jan 29 '14 at 3:28

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})$.
• "The boundary of every axis-parallel separating rectangle contains a horizontal or a vertical segment of length $\sqrt{n}/4$ inside Q" - shouldn't it be: $\sqrt{n}/2$? – Erel Segal-Halevi Jan 24 '14 at 9:18
• Here is an attempt to draw the construction (I took n=f(n)=16, and used 64 instead of 400): [1]: $m_1$ collections in a square grid: i.stack.imgur.com/6aGMA.png [2]: $m_2$ collections in horizontal rectangles: i.stack.imgur.com/TZ3X5.png [3]: $m_2$ collectins in vertical rectangles: i.stack.imgur.com/tTQmX.png – Erel Segal-Halevi Jan 24 '14 at 9:21
• @Erel Segal Halevi You are right, we can require $\sqrt{n}/2$; so I have changed it. I wrote $\sqrt{n}/4$ before, since my original goal was to intersect a "middle rectangle", centered around the axis of symmetry of $Q$. – Jan Kyncl Jan 24 '14 at 19:49