most recent 30 from http://mathoverflow.net 2013-06-18T06:58:58Z http://mathoverflow.net/feeds/question/79529 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79529/applications-of-ham-sandwich-type-results-references-a-general-principle Alfredo Hubard 2011-10-30T16:50:03Z 2011-11-02T23:40:49Z

<p>Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any that touches the most recent developments and includes some applications to both combinatorial geometry and functional analysis. Is there a good reference in which they are summarized? The following is a list of the applications that I know of. Do you know of other applications? Heuristically, what is a good principle to recognize problems in which these theorems might lead to a solution?</p> <p>Applications of the ham sandwich</p> <p>Alon-Akiyama disjoint rainbows theorem. Alon-West, Goldberg-West. Necklaces for the thieves theorem. Barany-Valtr, Pach. Same type lemma. Matousek, Agarwal-Erickson. Geometric Range Search. Gromov-Milman, Concentration of measure for uniformly convex bodies (localization technique).</p> <p>Polynomial Ham Sandwhich</p> <p>Guth's multilinear Kakeya estimate, Guth-Katz: Joints problem, Distinct distances problem. Tao-Solymosi, Matousek-Sharir-Kaplan Generalizations and new proofs of Szemeredi-Trotter, Sum product estimates, Existence of not too selfintersecting geometric tree of Chazelle and Welzl.</p> <p>Center Point Theorem</p> <p>Zivaljevic-Vrecica, Dolnikov. The Transversal Center Point Theorem. Thurston-Vavais-Miller-Teng. Separator theorem for planar graphs and for intersection graphs of metric euclidean balls with bounded overlap.</p> <p>The Yao-Yao partition</p> <p>Lehec. The Blashke-Santalo functional inequality. Alon-Pach-Radocic-Sharir-Pinchasi Semialgebraic same type lemma for graph-like relations. Fox-Gromov-Naor-Lafforgue-Pach, Bukh-Hubard. Semialgebraic same type lemma.</p> <p>Convex Equipartitions.</p> <p>Gromov, Memarian. Tight bounds on the Waist of the sphere for smooth maps. Karasev and Volovikov generalized Gromov's convex equpartitions theorem to obtain a Waist theorem for targets other than $R^k$.</p> <p>Sorry for the possible mistakes in the pseudocitations.</p>

http://mathoverflow.net/questions/79529/applications-of-ham-sandwich-type-results-references-a-general-principle/79877#79877 Joseph O'Rourke 2011-11-02T23:40:49Z 2011-11-02T23:40:49Z

<p>The chapter entitled "Topological Methods" by R.T. Živaljević, in the <em><a href="http://www.crcpress.com/product/isbn/9781584883012" rel="nofollow">Handbook of Discrete and Computational Geometry</a></em>, CRC Press, Chapter 14, 2004, is a good source.</p> <p>I believe ham-sandwich cuts play a role in regression depth computations, e.g., in the 2000 paper by Marshall Bern and David Eppstein, "<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.4562" rel="nofollow">Multivariate Regression Depth</a>."</p> <p>Since you consider the center-point theorem and the center-traversal theorem as applications of the ham-sandwich theorem, this leads to a different proof of the Lipton-Tarjan small-separator theorem for planar graphs, a connection established by Miller, Teng, Thurston, and Vavasis in "<a href="http://dl.acm.org/citation.cfm?id=256294" rel="nofollow">Separators for sphere-packings and nearest neighbor graphs</a>," <em>Journal of the ACM</em>, 1997.</p>