5
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Jan 14, 2014 at 13:33
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 14, 2014 at 17:04
  • $\begingroup$ Must the rectangle be axis-parallel too? $\endgroup$ Jan 20, 2014 at 0:37
  • 2
    $\begingroup$ 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$ $\endgroup$
    – fedja
    Jan 20, 2014 at 3:48
  • 1
    $\begingroup$ @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})$. $\endgroup$
    – Jan Kyncl
    Jan 29, 2014 at 3:28

1 Answer 1

3
+50
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ "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$? $\endgroup$ Jan 24, 2014 at 9:18
  • 1
    $\begingroup$ 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 $\endgroup$ Jan 24, 2014 at 9:21
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Jan Kyncl
    Jan 24, 2014 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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