A geometric separator is a line (or another shape) that partitions a collection of geometric shapes into two subsets, such that proportion of shapes in each subset is bounded, and the number of shapes that do not belong to any subset (i.e. the shapes intersected by the separator itself) is small. When a geometric separator exists, it can be used for building divide-and-conquer algorithms for solving various problems in computational geometry.
Separators that are lines
General question In 1979, Helge Tverberg raised the following question. For two positive integers k, l, what is the smallest number n(k,l) such that, for any family of pairwise-disjoint convex objects in the plane, there exists a straight line that has at least k objects on one side and at least l on the other side? The following results are known.
Obviously, n(1,1)=1. Hope and Katchalski proved that n(k,1) ≤ 12(k-1) for all k ≥ 2. Villanger proved that n(2,2) = ∞: he showed an infinite family of pairwise-disjoint segments such that no straight line has two segments in each side. Pach and Tardos showed a simpler construction using only unit segments, and another construction using only discs (or squares).
Separators for axes-parallel rectangles Given a set of N=4k disjoint axis-parallel rectangles in the plane, there is a line, either horizontal or vertical, such that at least N/4 rectangles lie entirely to each side of it (thus at most N/2 rectangles are intersected by the separator line).
Proof Define W as the most western vertical line with at least N/4 rectangles entirely to its west. There are two cases:
If there are at least N/4 rectangles entirely to the east of W, then W is a vertical separator. Otherwise, by moving W slightly to the west, we get a vertical line that intersects more than N/2 rectangles. Find a point on this line that has at least N/4 rectangles above and N/4 rectangles below it, and draw a horizontal separator through it.
Optimality
The number of intersected shapes, guaranteed by the above theorem, is O(N). This upper bound is asymptotically tight even when the shapes are squares, as illustrated in the figure to the right. This is in sharp contrast to the upper bound of O(√N) intersected shapes, which is guaranteed when the separator is a closed shape (see previous section).
Moreover, when the shapes are arbitrary rectangles, there are cases in which no line that separates more than a single rectangle can cross less than N/4 rectangles, as illustrated in the figure to the right.
Generalizations The above theorem can be generalized from disjoint rectangles to k-thick rectangles. Additionally, by induction on d, it is possible to generalize the above theorem to d dimensions and get the following theorem:
Given N axis-parallel d-boxes whose interiors are k-thick, there exists an axis-parallel hyperplane such that at least:
⌊ ( N + 1 − k ) / ( 2 d ) ⌋ {\displaystyle \lfloor (N+1-k)/(2d)\rfloor }
of the d-box interiors lie to each side of the hyperplane. For the special case when k = N − 1 (i.e. each point is contained in at most N − 1 boxes), the following theorem holds:
Given N axis-parallel d-boxes whose interiors are (N − 1)-thick, there exists an axis-parallel hyperplane that separates two of them. The objects need not be boxes, and the separators need not be axis-parallel:
Let C be a collection of possible orientations of hyperplanes (i.e. C = {horizontal,vertical}). Given N d-objects, such that every two disjoint object are separated by a hyperplane with an orientation from C, whose interiors are k-thick, there exists a hyperplane with an orientation from C such that at least: (N + 1 − k)/O(C) of the d-objects interiors lie entirely to each side of the hyperplane.
Algorithmic versions It is possible to find the hyperplanes guaranteed by the above theorems in O(Nd) steps. Also, if the 2d lists of the lower and upper endpoints of the intervals defining the boxes's ith coordinates are pre-sorted, then the best such hyperplane (according to a wide variety of optimality measures) may be found in O(Nd) steps.
Separators that are closed shapes A simple case in which a separator is guaranteed to exist is the following:
Given a set of n disjoint axis-parallel squares in the plane, there is a rectangle R such that, at most 2n/3 of the squares are inside R, at most 2n/3 of the squares are outside R, and at most O(sqrt(n)) of the squares are not inside and not outside R (i.e. intersect the boundary of R). Thus, R is a geometric separator that separates the n squares into two subset ("inside R" and "outside R"), with a relatively small "loss" (the squares intersected by R are considered "lost" because they do not belong to any of the two subsets).
Proof Define a 2-fat rectangle as an axis-parallel rectangle with an aspect ratio of at most 2. Let R0 be a minimal-area 2-fat rectangle that contains the centers of at least n/3 squares. Thus every 2-fat rectangle smaller than R0 contains fewer than n/3 squares. For every t in [0,1), let Rt be a 2-fat rectangle with the same center as R0, inflated by 1 + t.
… excerpt ends here. Continue reading the full article.
