Geometric separator

When a geometric separator exists, it can be used for building divide-and-conquer algorithms for solving various problems in computational geometry.

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?

Define W as the most western vertical line with at least N/4 rectangles entirely to its west.

There are two cases: 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.

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.

A simple case in which a separator is guaranteed to exist is the following:[5][6] 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).

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.

Therefore: Therefore, by the pigeonhole principle there is a certain j0 for which: The separator we look for is the rectangle Rt, where

[7] Using this separator theorem, we can solve certain problems in computational geometry in the following way: The above theorem can be generalized in many different ways, with possibly different constants.

Here is one such collection (from theorem 34 of [5]): Consider an equilateral triangle.

For example, start with a 1-by-Φ rectangle, where Φ is the golden ratio.

Add an adjacent Φ-by-Φ square and get another golden rectangle.

Add an adjacent (1+Φ)-by-(1+Φ) square and get a larger golden rectangle, and so on.

The existence of a centerpoint can be proved using Helly's theorem.

For a given point p and constant a>0, define Pr(a,p,o) as the probability that a random line through o lies at a distance of less than a from p. The idea is to bound this probability and thus bound the expected number of points at a distance less than a from a random line through o.

Then, by the pigeonhole principle, at least one line through o is the desired separator.

Bounded-width separators can be used for approximately solving the protein folding problem.

[9] It can also be used for an exact sub-exponential algorithm to find a maximum independent set, as well as several related covering problems, in geometric graphs.

[8] The planar separator theorem may be proven by using the circle packing theorem to represent a planar graph as the contact graph of a system of disks in the plane, and then by finding a circle that forms a geometric separator for those disks.