Algorithms for Ham-Sandwich Cuts
Jiri Matousek (joint work with Chi-Yuan Lo, William Steiger)
Department of Computer Science
Charles University, CSFR
Report B 92-20
September 92
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-20.ps.gz
Given disjoint sets $P_1,P_2,\ldots,P_d$ in $R^d$ with $n$ points in total, a
{\em \hs cut} is a hyperplane that simultaneously bisects the $P_i$.
We present algorithms for finding \hs cuts in every dimension $d >1$.
When $d=2$, the algorithm is optimal, having complexity $O(n)$. For
dimension $d>2$, the bound on the running time is
proportional to the worst-case time needed for constructing
a level in an arrangement of $n$ hyperplanes in dimension $d-1$.
This, in turn, is related to the number of $k$-sets
in $R^{d-1}$. With the current estimates,
we get complexity close to $O(n^{3/2})$ for $d=3$,
roughly $O(n^{8/3})$ for $d=4$ and
$O(n^{d-1-a(d)})$ for some
$a(d)>0$ (going to zero as $d$ increases) for larger $d$.
We also give a linear time
algorithm for \hs cuts in $R^3$ when the three sets are
suitably separated.