2026-07-19T23:58:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7232 2024-03-06T10:39:59Z ddc:004 open_access

Ham Sandwich is Equivalent to Borsuk-Ulam C. S., Karthik Saha, Arpan Ham Sandwich theorem Borsuk-Ulam theorem Query Complexity Hyperspherical Harmonics The Borsuk-Ulam theorem is a fundamental result in algebraic topology, with applications to various areas of Mathematics. A classical application of the Borsuk-Ulam theorem is the Ham Sandwich theorem: The volumes of any n compact sets in R^n can always be simultaneously bisected by an (n-1)-dimensional hyperplane. In this paper, we demonstrate the equivalence between the Borsuk-Ulam theorem and the Ham Sandwich theorem. The main technical result we show towards establishing the equivalence is the following: For every odd polynomial restricted to the hypersphere f:S^n->R, there exists a compact set A in R^{n+1}, such that for every x in S^n we have f(x)=vol(A cap H^+) - vol(A cap H^-), where H is the oriented hyperplane containing the origin with x as the normal. A noteworthy aspect of the proof of the above result is the use of hyperspherical harmonics. Finally, using the above result we prove that there exist constants n_0, epsilon_0>0 such that for every n>= n_0 and epsilon <= epsilon_0/sqrt{48n}, any query algorithm to find an epsilon-bisecting (n-1)-dimensional hyperplane of n compact set in [-n^4.51,n^4.51]^n, even with success probability 2^-Omega(n), requires 2^Omega(n) queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthik C. S. and Arpan Saha 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.24 urn:nbn:de:0030-drops-72325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.24 eng https://creativecommons.org/licenses/by/3.0/legalcode