I just recently learned the Ham Sandwich Theorem in my algebraic topology class. If we take the measure to be the counting measure and let $n=2$, then the theorem tells us that given a set of black and white points in the plane, we can draw a line that'll divide the plane so that there is an equal number of black and white points on either side of the line. But this theorem is existential only. Is there an algorithm for actually computing the line for this discrete case? If so, what's the complexity?


The paper by Lo, Matoušek, and Steiger entitled "Algorithms for Ham-Sandwich Cuts" gives an $O(n)$ algorithm, where $n$ is the number of points. That's the best you can do, since you need to consider all such points.

  • 4
    $\begingroup$ No, the paper gives a linear-time algorithm only in dimension 2. $\endgroup$
    – Boris Bukh
    Nov 16 '10 at 6:22
  • 3
    $\begingroup$ The 1994 paper is available here dominik.eigendynamik.ch/ethz/focus_ti/cgsem/… and as Boris Bukh points out only gives linear for $d=2$. In fact a linear time algorithm in $d=2$ was given by Lo and Steigler in 1990 (ref. 17 in this paper). For higher $d$, their algorithms are $O(n^{d-1-a(d)})$ with $a(d)$ tending to zero. $\endgroup$
    – j.c.
    Nov 16 '10 at 6:39
  • $\begingroup$ Not related to the original question, but there is a brand-spanking-new paper which proves that no $O(n^{o(d)})$-time algorithm exists, unless NP has subexponential-time algorithms. $\endgroup$ Nov 17 '10 at 19:09
  • 1
    $\begingroup$ D'oh the paper is <a href="page.mi.fu-berlin.de/dawerner/publications/…>, called "On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems" $\endgroup$ Nov 17 '10 at 19:09
  • $\begingroup$ I think there is a possible connection here with the Butty numbers for the de-Ham cohomology group, also known as De-Ham Butty numbers. $\endgroup$ Mar 31 '12 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.