Geometric separator

A geometric separator is a line (or other 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 closed shapes

A simple case in which a separator is guaranteed to exist is the following:[1][2]

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.

Now it remains to show that there is a t for which Rt intersects at most O(sqrt(n)) squares.

First, consider all the "large squares" – the squares whose side-length is at least \operatorname{width}(R_0) / 2 \sqrt{n}. For every t, the perimeter of Rt is at most 2·perimeter(R0) which is at most 6·width(R0), so it can intersect at most 12 \sqrt{n} large squares.

Next, consider all the "small squares" – the squares whose side-length is less than \operatorname{width}(R_0) / 2 \sqrt{n}.

For every t, define: intersect(t) as the set of small squares intersected by the boundary of Rt. For every t1 and t2, if |t_1-t_2| \geq 1/\sqrt{n}, then |\operatorname{width}(R_{t_1})-\operatorname{width}(R_{t_2})| \geq \operatorname{width}(R_0)/\sqrt{n}. Therefore there is a gap of at least \operatorname{width}(R_0) / 2 \sqrt{n} between the boundary of Rt1 and the boundary of Rt2. Therefore, intersect(t1) and intersect(t2) are disjoint. Therefore:

\sum_{j=0}^{\sqrt{n}-1}{|\operatorname{intersect}(j/\sqrt{n})|} \leq n

Therefore by the pigeonhole principle there is a certain j0 for which:

|\operatorname{intersect}(j_0/\sqrt{n})| \leq \sqrt{n}

The separator we look for is the rectangle Rt, where t = j_0/\sqrt{n}.[3]

Application example

Using this separator theorem, we can solve certain problems in computational geometry in the following way:

Generalizations

The above theorem can be generalized in many different ways, with possibly different constants. For example:

Optimality

The ratio of 1:2, in the square separator theorem above, is the best that can be guaranteed: there are collections of shapes that cannot be separated in a better ratio using a separator that crosses only O(sqrt(n)) shapes. Here is one such collection (from theorem 34 of [1]):

Consider an equilateral triangle. At each of its 3 vertices, put N/3 shapes arranged in an exponential spiral, such that the diameter increases by a constant factor every turn of the spiral, and each shape touches its neighbours in the spiral ordering. 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.

Now, in order to separate more than 1/3 of the shapes, the separator must separate O(N) shapes from two different vertices. But to do this, the separator must intersect O(N) shapes.

Separators that are hyperplanes

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:

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.[4]

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:[1]

Given N axis-parallel d-boxes whose interiors are k-thick, there exists an axis-parallel hyperplane such that at least:
\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:[1]

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 width-bounded strips between parallel hyperplanes

[5]

Let Q be a set of n points in the plane such that the minimal distance between points is d. Let a>0 be a constant.
There is a pair of parallel lines of distance a, such that at most 2n/3 points lie to each side of the strip, and at most 1.3 {a \over d} \sqrt{n} points lie inside the strip.
Equivalently: there is a line such that at most 2n/3 points lie to each side of it and at most 1.3 {a \over d} \sqrt{n} points lie at a distance of less than a/2 from it.

Proof sketch

Define the centerpoint of Q as a point o such that every line through it has at most 2n/3 points of Q in each side of it. 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.

Applications

Bounded-width separators can be used for approximately solving the protein folding problem.[6] 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.[5]

Geometric separators and planar graph separators

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.[7]

See also

Notes

  1. 1.0 1.1 1.2 1.3 1.4 Smith, W. D.; Wormald, N. C. (1998). "Geometric separator theorems and applications". Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). p. 232. doi:10.1109/sfcs.1998.743449. ISBN 0-8186-9172-7.
  2. 2.0 2.1 Chan, T. M. (2003). "Polynomial-time approximation schemes for packing and piercing fat objects". Journal of Algorithms 46 (2): 178–189. doi:10.1016/s0196-6774(02)00294-8.
  3. This proof is based on the more general proof of Chan (2003), but with the better constants of Smith&Wormald (1998).
  4. MvG (2013-09). "Cutting a cake without destroying the toppings". Math Stack Exchange. Retrieved 2014-01. Check date values in: |date=, |accessdate= (help)
  5. 5.0 5.1 Fu, B. (2011). "Theory and application of width bounded geometric separators". Journal of Computer and System Sciences 77 (2): 379–392. doi:10.1016/j.jcss.2010.05.003.
  6. Fu, B.; Wang, W. (2007). "Geometric Separators and Their Applications to Protein Folding in the HP-Model". SIAM Journal on Computing 37 (4): 1014. doi:10.1137/s0097539704440727.
  7. Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997). "Separators for sphere-packings and nearest neighbor graphs". J. ACM 44 (1): 1–29. doi:10.1145/256292.256294..
  8. Kyncl, Jan. "Simultaneous geometric separator". MathOverflow. Retrieved 4 February 2014.