Applications of geometric separator theorems
Warren D. Smith and Nicholas C. Wormald
ABSTRACT
The companion paper ``Geometric separator theorems''
proved a large number
of separator theorems about geometrical objects.
We now find geometric separator theorems about geometrical
{\em graphs}, and applications (mostly algorithmic) of them.
Examples:
{\tt I}: There exists a rectangle crossed by the minimal spanning
tree of $N$ sites
in the plane $\le (4 \cdot 3^{1/4} + o(1)) \sqrt{N}$ times, having
$\le 2N/3$ sites inside and outside.
{\tt II}: Similar results for
other geometrical graphs such as minimum matchings and traveling
salesman tours, and in arbitrary dimensions.
{\tt III}: $E$-edge 2-connected torus (or Klein bottle)
graphs, each of whose valencies and face sizes are $\ge 3$,
have a $1/3$-$2/3$ separator with $\le (4+o(1)) \sqrt{E}$
vertices in the separator. The separator corresponds to a simple
closed curve.
{\tt IV}: We exhibit $V$-vertex planar graphs such that any $1/3$-$2/3$
separator must have cardinality$\ge \sqrt{5V/2}$.
{\tt V}: We present the first subexponential algorithms for
optimal traveling salesman tour and rectilinear
Steiner tree of $N$ points in $d$-space, $d$ fixed.
The runtime if $d \ge 2$ is fixed is $N^{O(N^{1-1/d})}$.
The same runtime bound applies for finding a $1 + O(N^{-p})$ times
optimal length Steiner tree in the Euclidean norm if $p > 0$
is fixed.
{\tt VI}: Algorithm to determine all intersection relationships
among $N$ convex $d$-bodies with aspect ratios bounded by $B$.
If a point of space can be in at most $\kappa$ of the bodies
(i.e. they are ``$\kappa$-thick''),
then the runtime is $(\log N + \kappa B^d C) d^{O(d)} N$
and the memory requirement is $d^{O(d)} N$, where $C$ is
the amount of time required to test if two given objects
intersect.
{\tt VII}: Solve linear systems whose graph structure is
an intersection graph as in VI, in
$O ( [ d \kappa^{1/d} B N^{1-1/d}]^\omega )$
time, $\omega < 2.376$.
{\tt VIII}: New data structure with $O(\log N)$ query time,
$O(N)$ space consumption, and $O(N \log N)$ build time,
to support point location among
$N$ convex boundedly thick convex bodies of
bounded aspect ratios in bounded dimension.
{\tt IX}: New algorithms for obstacle avoiding short paths among
boundedly thick obstacles of bounded aspect ratio in the plane.
E.g. this may be solved in preprocessing time
$O(N^{3/2} \log N )$
with storage
$O(N \log N)$
and query time
$O ( \log N )$ to report a path $3.01$ times longer
than optimal (in the $L_1$ obstacle avoiding metric)
between any two given points.
KEYWORDS
Separator theorems, Steiner minimal tree, Rectilinear Steiner minimal
tree, traveling salesman tour, minimum spanning tree, spanners,
banyans, minimum matching, pigeonhole principle, torus graphs,
planar graphs, point location, computational geometry,
discrete isoperimetric theorems, Delaunay triangulation,
Gabriel graph, universal graphs, nested dissection,
obstacle avoiding shortest paths.