火腿三明治定理

火腿三明治定理（英语：Ham sandwich theorm），也被称为Stone-Tukey定理，它在测度论中有重要的意义。火腿三明治定理说明在n-维空间中有n个可测量的“物体”，可以用一个(n-1)-维的超平面把它们同时分成测度相等的两部分。

命名

当 n=3 时，就像一个三明治一样——这里的三个“物体”则是两片面包和中间的火腿。用一个平面可以同时把三个“物体”截断。

二维版本的证明：“旋转刀片”

二维版本的证明比任意维度的证明较为简单，流程如下：

对任何角度 ，均存在一条与 X 轴成角度 的直线平分第一个物体。（需使用介值定理） 令 由 0 增加到  ，再使用介值定理，则存在一条直线同时平分第二个物体。

定理的离散版本

离散版本可以视为定理的特例，当中每一个＂物体＂都是用有限个点组成的集合，并使用计数测度。但需要考虑点刚好落左超平面上时的情况。

参考文献

  • Beyer, W. A.; Zardecki, Andrew, The early history of the ham sandwich theorem, American Mathematical Monthly, 2004, 111 (1): 58–61, JSTOR 4145019, doi:10.2307/4145019 .
  • Edelsbrunner, Herbert; Waupotitsch, R., Computing a ham sandwich cut in two dimensions, Journal of Symbolic Computation, 1986, 2: 171–178, doi:10.1016/S0747-7171(86)80020-7 .
  • Lo, Chi-Yuan; Steiger, W. L., An optimal time algorithm for ham-sandwich cuts in the plane, Proceedings of the Second Canadian Conference on Computational Geometry: 5–9, 1990 .
  • Lo, Chi-Yuan; Matoušek, Jiří; Steiger, William L., Algorithms for Ham-Sandwich Cuts, Discrete and Computational Geometry, 1994, 11: 433–452, doi:10.1007/BF02574017 .
  • Megiddo, Nimrod, Partitioning with two lines in the plane, Journal of Algorithms, 1985, 6: 430–433, doi:10.1016/0196-6774(85)90011-2 .
  • Smith, W. D.; Wormald, N. C., Geometric separator theorems and applications, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280): 232, 1998, ISBN 0-8186-9172-7, doi:10.1109/sfcs.1998.743449 
  • Steinhaus, Hugo, A note on the ham sandwich theorem, Mathesis Polska, 1938, 9: 26–28 .
  • Stone, Arthur H.; Tukey, John W., Generalized "sandwich" theorems, Duke Mathematical Journal, 1942, 9: 356–359 [2019-06-14], doi:10.1215/S0012-7094-42-00925-6, （原始内容存档于2020-08-26） .
  • Stojmenovíc, Ivan, Bisections and ham-sandwich cuts of convex polygons and polyhedra., Info. Processing Letts., 1991, 38 (1): 15–21 .