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
  • 1
    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
  • 2
    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
  • 1
    @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
up vote 3 down vote accepted
+50

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})$.

  • 1
    "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
  • 1
    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
  • 1
    @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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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