ハムサンドイッチ定理

数学の測度論では、任意の正の整数 $n$ に対して、ハムサンドイッチ定理は、 $n$ 次元ユークリッド空間に $n個$ の測定可能な「オブジェクト」がある場合、単一の $($ $n$ $- 1)$ 次元超平面を使用して、それらのそれぞれを半分に分割できることを述べています (測定、たとえば体積に関して) 。これは、オブジェクトが重なり合っている場合でも可能です。

これはヒューゴ・シュタインハウスによって提案され、シュテファン・バナッハによって証明されました（ $n$ 次元の場合の定理は述べずに、3次元で明示的に証明されました）。また、数年後にはアーサー・H・ストーンとジョン・テューキーにちなんでストーン・テューキーの定理とも呼ばれました。

ネーミング

ハムサンドイッチ定理は、 $n = 3$ で、二等分される 3 つの物体がハムサンドイッチの材料である場合にその名前が付けられています。これらの 3 つの材料が、パン 2 枚とハム 1 枚 (Peters 1981)、パンとチーズとハム (Cairns 1963)、またはパンとバターとハム (Dubins & Spanier 1961) であるかどうかについては、出典が異なります。2 次元では、この定理は、線で二等分される 2 つの物体が平坦であることを示すパンケーキ定理として知られています(Cairns 1963)。

歴史

Beyer & Zardecki (2004) によると、ハムサンドイッチ定理、具体的には $n = 3 の$ 場合に 3 つの立体を平面で二等分する方法に関する最も古い論文は、1938 年にポーランドの数学雑誌に掲載された論文 (Editors 1938) です。Beyer と Zardecki の論文にはこの論文の翻訳が含まれており、この問題の提起はHugo Steinhausによるものとされ、Borsuk-Ulam 定理への還元によってStefan Banach が最初にこの課題を解決したとされています。この論文では、2 つの方法で問題を提起しています。1 つ目は形式的に「適切な平面を使用して、任意の場所にある 3 つの立体を常に二等分することは可能か」、2 つ目は非形式的に「ハムを肉切り器の下に置くと、肉、骨、脂肪が半分に切断されるか」です。

より新しい参考文献は、Stone & Tukey (1942) であり、これが「Stone–Tukey 定理」という名前のもとになっています。この論文では、測度を含むより一般的な設定で、定理の $n次元バージョンを証明しています。この論文では、査読者からの情報に基づいて、$ $n = 3 の$ 場合をStanislaw Ulamに帰しています。しかし、Beyer & Zardecki (2004) は、上記の注釈を考慮して、これは誤りであると主張しています。ただし、「Ulam は Borsuk –Ulam 定理の提案に基本的な貢献をした」と述べています。

2次元変形：回転ナイフを使った証明

定理の2次元版（パンケーキ定理とも呼ばれる）は、公正なケーキカットの文献に出てくる議論によって証明できる（例えば、ロバートソン・ウェッブ回転ナイフ手順を参照）。

各角度について、角度の直線 (「ナイフ」) はパンケーキ #1 を二等分できます。これを確認するには、角度の直線をその法線に沿ってからまで平行移動します。直線で覆われるパンケーキ #1 の割合は 0 から 1 まで連続的に変化するため、中間値定理により、途中のどこかで 1/2 に等しくなります。直線の全範囲の平行移動で 1/2 の割合が得られる可能性があります。この場合、そのようなすべての平行移動の中央を選択するのが標準的な選択です。 $\alpha \in [0,180^{\circ }]$ $\alpha$ $\alpha$ $-\infty$ $\infty$

ナイフの角度が 0 のとき、パンケーキ #2 も切り分けられますが、おそらく切り分けられた部分は等しくありません (運が良ければ、切り分けられた部分は等しくなります)。ナイフの「正」の側を、パンケーキ #2 の割合が大きい側と定義します。次にナイフを回転させ、上記のように平行移動します。角度がのとき、をナイフの正の側でのパンケーキ #2 の割合として定義します。最初はです。角度がわずかに変化するとナイフの位置もわずかに変化するため、関数は連続的です。 $\alpha$ $p(\alpha )$ $p(0)>1/2$ $p$

ナイフの角度が 180 のとき、ナイフは逆さまになっているので、です。中間値定理により、となる角度が存在するはずです。その角度で切ると、両方のパンケーキが同時に二等分されます。 $p(180)<1/2$ $p(\alpha )=1/2$

ん次元変種: ボルスク・ウラム定理を用いた証明

ハムサンドイッチ定理は、ボルスク・ウラム定理を用いて次のように証明できる。この証明は、 $n$ $= 3 の$ 場合について、スタインハウスら (1938) がシュテファン・バナッハに帰属する証明に従っている。同変位相幾何学の分野では、この証明は配置空間/テストマップパラダイムに分類される。

$A 1 、 A 2 、...、 An$ で $、$ $同時に二等分するn 個$ のオブジェクトを表すものとします。S $を、$ 原点を中心とする $n$ 次元ユークリッド空間に埋め込まれた単位 $(n - 1)$ 球面とします。球面 $S$ の表面上の各点 $p$ について、原点から $pへの ($ 法)ベクトルに垂直な方向付けられたアフィン超平面(必ずしも中心が 0 である必要はない)の連続体を定義できます。各超平面の「正の側」は、そのベクトルが指す側として定義されます (つまり、方向は選択できます)。中間値定理により、このような超平面のすべての族には、境界付きオブジェクト $A$ $n を$ 二等分する超平面が少なくとも 1 つ含まれます。つまり、一方の極端な移動では、 $A$ $n$ のどの体積も正の側になく、もう一方の極端な移動では、 $A$ $n$ $の体積全体が正の側にあるため、その間には、 A$ $n$ の体積の半分が正の側にある移動が必ず存在します。族内にそのような超平面が複数ある場合は、 $A$ $n$ が二等分される変換区間の中点を選択することで、標準的に 1 つを選ぶことができます。このようにして、球面 $S上の各点$ $p$ に対して、原点から $p$ へのベクトルに垂直で $A$ $n を$ $二等分する超平面π$ $($ $p$ $)$ が得られます。 $\mathbb {R} ^{n}$

$ここで、 ($ $n$ $-1)$ 球面 $S$ から $($ $n$ $-1)$ 次元ユークリッド空間への関数 $fを$ 次のように定義します。 $\mathbb {R} ^{n-1}$

f (p) = (

π

(

p

)

の正の側にある

A 1

の体積、

π

(

p

)

の正の側にある

A

2

の体積、 ...、

π

(

p

)の正の側に

あるA

n

-1

の体積)

。

この関数 $f は$ 連続です(正式な証明では、何らかの正当化が必要になります)。Borsuk-Ulam の定理により、球面 $S上には$ $f$ $($ $p$ $) =$ $f$ $($ $q$ $)$ となる対心点 $p$ と $q$ があります。対心点 $p$ と $q は、$ 正の辺が反対であることを除いて等しい超平面 $π$ $($ $p$ $)$ と $π$ $($ $q$ $)に対応します。したがって、$ $f$ $($ $p$ $) =$ $f$ $($ $q$ $)は、$ $i$ $= 1, 2, ...,$ $n$ $-1に対して、$ $A$ $i$ の体積が π ( p ) (または π ( q ) ) の正の辺と負の辺で同じであることを意味します $。$ $したがって$ $、 π ( p$ $)$ (または $π$ $($ $q$ $)$ )は、 $A$ $1$ $、$ $A$ 2 $、$ $...$ $,$ $A$ $n$ $の$ $体積$ $を$ $同時に$ $二$ $等分$ $する$ 、目的のハムサンドイッチカットです。

測度理論バージョン

測度論において、ストーンとテューキー (1942) はハムサンドイッチ定理のより一般的な形式を 2 つ証明しました。どちらのバージョンも、共通集合 $Xの$ $n個の$ 部分集合 $X 1 、 X 2 、...、 X n$ の二分に関するもので、ここで $X は$ カラテオドリー外測度を持ち、各 $X$ $i は$ 有限外測度を持ちます。

彼らの最初の一般的な定式化は次のとおりです。任意の連続実関数に対して、 $n$ 次元球面 $S$ $n$ の点 $p$ と実数s ₀が存在し、曲面 $f$ $($ $p$ $,$ $x$ $) =$ $s$ $0$ $はXを等しい測度の$ $f$ $($ $p$ $,$ $x$ $) <$ $s$ $0$ と $f$ $($ $p$ $,$ $x$ $) >$ $s$ $0$ に分割し、同時に $X$ $1$ $、$ $X$ $2$ $、...、$ $X$ $n$ の外測度を二等分します。証明は、再び Borsuk-Ulam の定理への還元です。この定理は、 $f$ $($ $s$ $、$ $x$ $) =$ $s$ $1$ $x$ $1$ $+ ... +$ $s$ $n$ $x$ $n$ とすることで、標準的なハムサンドイッチ定理を一般化します。 $f\colon S^{n}\times X\to \mathbb {R}$

彼らの 2 番目の定式化は次のとおりです。 $X$ 上の任意の $n + 1 個$ の測定可能な関数 $f 0 、 f 1 、...、 f n$ が $X$ の任意の部分集合に対して線型独立である場合、線型結合 $f$ $=$ $a$ $0$ $f$ $0$ $+$ $a$ $1$ $f$ $1$ $+ ... +$ $a$ $n$ $f$ $n$ が存在し、 $X を$ $f$ $($ $x$ $) < 0$ と $f$ $($ $x$ $) > 0$ に分割する曲面 f ( x ) = 0 が $、$ $同時に$ $X$ $1$ $、$ $X$ $2$ $、$ $...$ $、$ $X$ $n$ の外測度を二等分します。この定理は、 $f$ $0$ $($ $x$ $) = 1$ とし、 $i$ $> 0の$ $f$ $i$ $($ $x$ $)を$ $xの$ $i$ 番目の座標とすることで、標準的なハムサンドイッチ定理を一般化したものです。

離散幾何学と計算幾何学のバージョン

離散幾何学と計算幾何学において、ハムサンドイッチ定理は通常、分割される各集合が点の有限集合である特殊なケースを指します。ここで関連する測度は計数測度であり、これは単に超平面の両側にある点の数を数えるものです。2次元では、定理は次のように述べることができます。

平面上の有限の点の集合（それぞれが「赤」または「青」の色）に対して、赤い点と青い点を同時に二等分する線が存在します。つまり、線の両側にある赤い点の数は等しく、線の両側にある青い点の数も等しくなります。

例外的に、点が線上にある場合があります。この状況では、これらの各点を線の片側、反対側、またはどちら側にも存在しない (点によって異なる可能性があります) としてカウントします。つまり、「二分する」とは、実際には各側に含まれる点の総数が半分未満であることを意味します。この例外的なケースは、赤い点の数または青い点の数が奇数の場合はもちろん、点の数が偶数である特定の構成でも定理が成立するために実際に必要です。たとえば、すべての点が同じ線上にあり、2 つの色が互いに離れている場合 (つまり、色が線に沿って交互にならない) などです。各側の点の数が互いに一致しない状況は、前の構成で線の外に余分な点を追加することによって提供されます。

計算幾何学では、このハムサンドイッチ定理は計算上の問題、ハムサンドイッチ問題につながります。2次元では、問題は次のようになります。平面上の有限の $n$ 点の集合が与えられ、それぞれが「赤」または「青」に色付けされ、それらの点に対するハムサンドイッチの切り方を見つけます。最初に、Megiddo (1985) は、特別な分離されたケースのアルゴリズムを説明しました。ここでは、すべての赤い点が何らかの線の片側にあり、すべての青い点が反対側にあります。これは、Megiddo が線形時間で見つけることができた唯一のハムサンドイッチの切り方がある状況です。後に、Edelsbrunner と Waupotitsch (1986) は、一般的な2次元の場合のアルゴリズムを示しました。彼らのアルゴリズムの実行時間は $O (n log n)$ で、記号 $Oは$ Big O 表記法の使用を示します。最後に、Lo と Steiger (1990) は最適な $O (n)$ 時間アルゴリズムを見つけました。このアルゴリズムは、Lo、Matoušek & Steiger (1994) によって高次元に拡張され、実行時間はです。 $d次元空間の一般的な位置にある$ $d$ 組の点が与えられると、アルゴリズムは、両方の半空間内の各集合の点の数が等しい $($ $d$ $-1)$ 次元超平面、つまり、与えられた点のハムサンドイッチカットを計算します。 $d が$ 入力の一部である場合、多項式時間アルゴリズムは存在しないと予想されます。これは、点がモーメント曲線上にある場合、問題がネックレス分割と同等になり、PPA 完全になるからです。 $o(n^{d-1})$

2 つの互いに交わらない凸多角形を面積二等分する線形時間アルゴリズムは、Stojmenovíc (1991) によって説明されています。

一般化

元の定理は最大 $n$ 個のコレクションに対して有効です。ここで $n$ は次元数です。高次元に行かずに多数のコレクションを二分するには、超平面の代わりに、次数 $k$ の代数面、つまり次数 $k$ の多項式関数で定義される( $n$ $-1$ ) 次元面を使用することができます。

$n$ 次元空間の測度が与えられた場合、それらすべてを二分する $k$ 次の代数曲面が存在する。(Smith & Wormald (1998)) ${\binom {k+n}{n}}-1$

$この一般化は、 n$ 次元平面を 5 次元平面にマッピングし、元の定理を適用することで証明されます。たとえば、 $n$ $= 2$ および $k$ $= 2$ の場合、2 次元平面は次のように 5 次元平面にマッピングされます。 ${\binom {k+n}{n}}-1$

(x, y) \to (x, y, x 2, y 2, xy)

です。

参照

正確な除算

参考文献

ベイヤー、WA; ザルデッキ、アンドリュー (2004)、「ハムサンドイッチ定理の初期の歴史」、アメリカ数学月刊誌、111 (1): 58–61、doi :10.2307/4145019、JSTOR 4145019、ProQuest 203746537。
ケアンズ、スチュワート S. (1963 年春)、「ネットワーク、ハムサンドイッチ、パテ」、Pi Mu Epsilon Journal、3 (8): 389–403、JSTOR 24338222。
Dubins, LE ; Spanier, EH (1961 年 1 月)、「ケーキを公平に切る方法」、American Mathematical Monthly、68 (1P1): 1–17、doi :10.1080/00029890.1961.11989615
エデルスブルンナー、ハーバート; ワウポティッチ、R. (1986)、「2次元でカットされたハムサンドイッチの計算」、シンボリック計算ジャーナル、2 (2): 171–178、doi : 10.1016/S0747-7171(86)80020-7。
Lo, Chi-Yuan; Steiger, WL (1990)、「平面におけるハムサンドイッチカットの最適時間アルゴリズム」、第 2 回カナダ計算幾何学会議の議事録、pp. 5–9。
Lo, Chi-Yuan; Matoušek, Jiří ; Steiger, William L. (1994)、「ハムサンドイッチカットのアルゴリズム」、離散および計算幾何学、11 (4): 433–452、doi : 10.1007/BF02574017。
メギド、ニムロッド（1985）、「平面上の2本の線による分割」、アルゴリズムジャーナル、6（3）：430-433、doi：10.1016/0196-6774（85）90011-2。
ピーターズ、ジェームズ V. (1981 年夏)、「ハムサンドイッチ定理と関連する結果」、ロッキーマウンテン数学ジャーナル、11 (3): 473–482、doi : 10.1216/RMJ-1981-11-3-473、JSTOR 44236614。
Smith, WD; Wormald, NC (1998)、「幾何学的セパレータ定理とその応用」、Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280)、p. 232、doi :10.1109/sfcs.1998.743449、ISBN 0-8186-9172-7、S2CID 17962961
編集者 (1938)、「Notatki: Z topologii」、Mathesis Polska (ポーランド語)、11 (1–2): 26–28。
ストーン、アーサー H. ;テューキー、ジョン W. (1942)、「一般化された「サンドイッチ」定理」、デューク数学ジャーナル、9 (2): 356–359、doi :10.1215/S0012-7094-42-00925-6。
ストイメノヴィッチ、イヴァン（1991）、「凸多角形と多面体の二分法とハムサンドイッチカット」、情報処理レター、38（1）：15–21、doi：10.1016/0020-0190（91）90209-Z。

外部リンク

ワイスタイン、エリック W.、「ハムサンドイッチ定理」、MathWorld
ハムサンドイッチ定理に関する数学用語の最も古い使用例
ハムサンドイッチカット by ダニエル・マクネヴィン
インタラクティブな2Dデモンストレーション