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.