TITLE
Geometric Separator Theorems \& Applications

AUTHORS
Warren D. Smith 
 NECI
Nicholas C. Wormald  
 Dept of Mathematics and Statistics, 
 University of Melbourne, Parkville
 VIC 3052, Australia. Research supported by the ARC.

ABSTRACT
We find a large number of ``geometric separator theorems'' such as:

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.

II: There exists a rectangle that is crossed by the minimal spanning
tree of $N$ sites in the plane at $\le (4 \cdot 3^{1/4} + o(1))
\sqrt{N}$ points, having $\le 2N/3$ sites inside and outside.

These theorems yield a large number of applications, such as
subexponential algorithms for traveling salesman tour and rectilinear
Steiner minimal tree in ${\bf R}^d$, new point location
algorithms, and new upper and lower bound proofs for ``planar
separator theorems.''