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: 
File:   pub/reports/
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.