Geometric separator theorems
Warren D. Smith and Nicholas C. Wormald 1998
ABSTRACT
We have a 4-step method for producing ``separator theorems'' about
geometrical objects en masse.
Examples:
{\tt I}:
Given $N$ disjoint iso-oriented squares in the plane, there exists
a rectangle with $\le 2N/3$ squares inside, $\le 2N/3$ squares
outside, and $\le (4 + o(1)) \sqrt{N}$ partly in \& out.
{\tt II}:
More generally, given $N$ iso-oriented $d$-cubes in $d$-space,
no more than $\kappa$ of which cover a point,
there exists a box with $\le 2N/3$ cubes inside, $\le 2N/3$ cubes
outside, and $O(d \kappa^{1/d} N^{1-1/d})$ partly in \& out.
Here ``$2/3$'' is best possible, and the dependence of the
bound on $\kappa$, $d$, and $N$ is best possible up to the absolute
constant factor in the $O$.
{\tt III}:
We have more general versions where the ``$d$-cubes'' and/or
the separating ``box'' could instead
be any of a wide variety of convex objects with bounded diameter/width
ratios, and where the disjointness condition can be replaced with a
variety of other conditions: (a) no more than $\kappa$ objects cover a point,
or (b) no subcollection's measure exceeds the union of its measures by
more than a factor $\kappa$, or (c) no more than $\kappa$ objects,
among objects whose linear dimensions vary by a factor at most
$\lambda$, cover a point.
For tons of applications of these theorems,
see the companion paper
``Applications of geometric separator theorems.''
For example, we get the first subexponential algorithms for
optimal traveling salesman tour and rectilinear
Steiner tree of $N$ points in $d$-space, $d$ fixed.
KEYWORDS
Separator theorems, centerpoints, sandwich theorems, cube
tiling, Hadwiger hypothesis, pigeonhole principle,
Vapnik-Chervonenkis dimension, computational geometry, covering problems.