Abstract
The Borsuk–Ulam theorem has many applications in algebraic topology, algebraic geomtry, and combinatorics. Here we study some combinatorial consequences, typically asserting the existence of a certain combinatorial object. An interesting aspect is the computational complexity of algorithms that search for the object. The study of these algorithms is facilitated by direct combinatorial existence proofs that bypass Borsuk–Ulam.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akiyama, J., Alon, N.: Disjoint simplices and geometric hypergraphs. In: Blum, G.S., Graham, R.L., Malkevitch, J. (eds.) Combinatorial mathematics. Proceedings of the Third International Conference, New York, NY 1985. Annals of the New York Academy of Sciences, vol. 555, pp. 1–3 (1989)
Alon, N.: Splitting necklaces. Adv. Math. 63, 247–253 (1987)
Alon, N.: Some recent combinatorial applications of Borsuk-type theorems. In: Deza, M.M., Frankl, P., Rosenberg, I.G. (eds.) Algebraic, extremal and metric combinatorics, Cambridge University Press, Cambridge, England, pp. 1–12 (1988)
Alon, N., West, D.: The Borsuk–Ulam theorem and bisection of necklaces. Proc. Amer. Math. Soc. 98, 623–628 (1986)
Avis, D.: On the partitionability of point sets in space. Proceedings of First ACM Symposium on Computational Geometry, pp. 116–120 (1985)
Bárány, I.: Geometric and combinatorial applications of Borsuk’s theorem. New trends in discrete and computational geometry. In: Pach, J. (ed.) Algorithms and combinatorics, vol. 10, pp. 235–249, Springer, Berlin (1993)
Bárány, I., Matoušek, J.: Simultaneous partitions of measures by k-fans. Discrete Comput. Geom. 25, 317–334 (2001)
Bárány, I., Matoušek, J.: Equipartition of two measures by a 4-fan. Discrete Comput. Geom. 27, 293–301 (2002)
Bereg, S.: Equipartitions of measures by 2-fans. Discrete Comput. Geom. 34(1), 87–96 (2005)
Bespamyatnikh, S., Kirkpatrick, D., Snoeyink, J.: Generalizing ham-sandwich cuts to equitable subdivisions. Discrete Comput. Geom. 24, 605–622 (2000)
Bose, P., Langerman, S.: Weighted ham-sandwich cuts. In: Kano, M., Akiyama, J. (eds.) Lecture Notes in Computer Science (JCDCG 2004: Japan Conference on Discrete and Computational Geometry, Tokyo, Japan, Springer, Heidelberg, (2005) (to appear)
Bose, P., Demaine, E., Hurtado, F., Iaconc, J., Langerman, S., Morin, P.: Geodesic ham-sandwich cuts. In: Proceedings of 20th ACM Symposium on Computational Geometry, pp. 1–9 (2004)
Buck, R., Buck, E.: Equipartitioning of convex sets. Math. Mag. 22, 195–198 (1987)
Cole, R., Sharir, M., Yap, C.: On k-hulls and related topics. SIAM J. Comput. 16, 61–77 (1987)
Cole, R., Salowe, J., Steiger, W., Szemerédi, E.: An optimal time algorithm for slope selection. SIAM J. Comp. 18, 792–810 (1989)
Courant, R., Robbins, H.: What is mathematics? Oxford University Press, New York (1941)
Dey, T.: Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19, 373–382 (1998)
Dobkin, D., Edelsbrunner, H.: Ham-sandwich theorems applied to intersection problems. In: Proceedings of 10th International Workshop on Graph Theoretic Concepts in Computer Science, pp. 88–99 (1984)
Edelsbrunner, H.: Algorithms in combinatorial geometry. Springer, Berlin, (1987)
Ito, H., Uehara, H., Yokoyama, M.: Two dimensional ham-sandwich theorem for partitioning into three convex pieces. In: Kano, M., Akiyama, J. (eds.) Lecture Notes in Computer Science 1763 JCDCG 1998: Japan Conference on Discrete and Computational Geometry, Tokyo, Japan, Springer, Heidelberg (2000)
Kaneko, A., Kano, M.: Balanced partitions of two sets of points in the plane. Comput. Geom. Theory Appl. 13, 253–261 (1999)
Langerman, S., Steiger, W.: Optimization in Arrangements. In: Alt, H., Habib, M. (eds.) Lecture Notes in Computer Science 2607 (STACS 2003: 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, pp. 50–61, Springer, Heidelberg (2003)
Lo, C.-Y., Matoušek, J., Steiger, W.: Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, 433–452 (1994)
Matoušek, J.: Using the Borsuk–Ulam theorem. Springer, Heidelberg (2003)
Megiddo, N.: Partitioning with two lines in the plane. J. Algorithms 6, 430–433 (1985)
Sakai, T.: Balanced convex partitions of measures in R2. Graphs Comb. 18, 169–192 (2002)
Schulman. L.: An equipartition of planar sets. Discrete Comput. Geom. 9, 257–266 (1992)
Sharir, M., Smorodinsky, S., Tardos, G.: An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26, 195–204 (2001)
Willard, D.: Polygon retrieval. SIAM J. Comput. 11, 149–165 (1982)
Yao, F., Dobkin, D., Edelsbrunner, H., Paterson, M.: Partitioning space for range queries. SIAM J. Comput. 18, 371–384 (1989)
Goldberg, C., West, D.: Bisection of circle colorings. SIAM J. Matrix Analysis App. 6, 93–106 (1985)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Roy, S., Steiger, W. Some Combinatorial and Algorithmic Applications of the Borsuk–Ulam Theorem. Graphs and Combinatorics 23 (Suppl 1), 331–341 (2007). https://doi.org/10.1007/s00373-007-0716-1
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-007-0716-1