most recent 30 from http://mathoverflow.net 2013-05-22T10:31:48Z http://mathoverflow.net/feeds/question/46196 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46196/algorithm-for-ham-sandwich-with-points Alan Guo 2010-11-16T05:50:44Z 2010-11-17T10:02:51Z

<p>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?</p>

http://mathoverflow.net/questions/46196/algorithm-for-ham-sandwich-with-points/46200#46200 Charles Chen 2010-11-16T06:04:21Z 2010-11-17T10:02:51Z

<p>The paper by Lo, Matoušek, and Steiger entitled <em>"Algorithms for Ham-Sandwich Cuts"</em> 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.</p>