ミンコフスキー加算

幾何学では、ユークリッド空間における2組の位置ベクトルAとBのミンコフスキー和は、Aの各ベクトルをBの各ベクトルに加えることによって形成されます。

${\displaystyle A+B=\{\mathbf {a} +\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in B\}}$

ミンコフスキー差（ミンコフスキー減算、ミンコフスキー分解、幾何差とも呼ばれる）^[1]は対応する逆であり、Bと加算してAを復元できる集合を生成する。これは、 Aの補集合とBを原点について反射したミンコフスキー和の補集合として定義される。 ^[2]${\displaystyle (AB)}$

${\displaystyle -B=\{\mathbf {-b} \,|\,\mathbf {b} \in B\}}$

${\displaystyle AB=(A^{\complement }+(-B))^{\complement }}$

この定義により、ミンコフスキー和と差の間に対称的な関係が生まれます。Bとの和と差を交互に取ることは必ずしも同等ではないことに注意してください。和は差が再び開くことのないギャップを埋めることができ、差は和が何もないところから再現できない小さな島を消すことができます。

${\displaystyle (AB)+B\subseteq A}$

${\displaystyle (A+B)-B\supseteq A}$

${\displaystyle AB=(A^{\complement }+(-B))^{\complement }}$

${\displaystyle A+B=(A^{\complement }-(-B))^{\complement }}$

2D画像処理では、ミンコフスキー和とミンコフスキー差は膨張と収縮として知られています。

ミンコフスキー差の別の定義は、凸形状の交差を計算するために使用されることがあります。^[3]これは前の定義と同じではなく、和演算の逆でもありません。代わりに、ミンコフスキー和のベクトル加算をベクトル減算に置き換えます。2つの凸形状が交差する場合、結果の集合には原点が含まれます。

${\displaystyle AB=\{\mathbf {a} -\mathbf {b} \,|\,\mathbf {a} \in A,\ \mathbf {b} \in B\}=A+(-B)}$

この概念はヘルマン・ミンコフスキーにちなんで名付けられました。

例えば、2つの集合AとB があり、それぞれが3つの位置ベクトル（非公式には3つの点）で構成され、 2つの三角形の頂点を表し、座標が ${\displaystyle \mathbb {R} ^{2}}$

${\displaystyle A=\{(1,0),(0,1),(0,-1)\}}$

そして

${\displaystyle B=\{(0,0),(1,1),(1,-1)\}}$

すると、ミンコフスキー和は

${\displaystyle A+B=\{(1,0),(2,1),(2,-1),(0,1),(1,2),(1,0),(0,-1),(1,0),(1,-2)\},}$

六角形の頂点と中心から構成されます。

ミンコフスキー加算では、零ベクトル0のみを含む零集合は単位元である。ベクトル空間の 任意の部分集合Sに対して、${\displaystyle \{0\},}$

${\displaystyle S+\{0\}=S.}$

空集合はミンコフスキー加算において重要です。なぜなら、空集合は他のすべての部分集合を消滅させるからです。ベクトル空間の すべての部分集合Sについて、空集合との和は空になります。

${\displaystyle S+\emptyset =\emptyset .}$

別の例として、実数または複素数である体における開球または閉球のミンコフスキー和を考えてみましょう。が においてを中心とする半径 の閉球である場合、任意の に対してが成り立ち、積が定義される任意のスカラー に対しても成り立ちます(または のときに発生します)。と がすべてゼロでない場合、を を中心とする閉球ではなく開球として定義した場合と同じ等式が依然として成立します(半径 の開球は空集合であるため、ゼロでない仮定が必要です)。 閉球と開球のミンコフスキー和は開球です。より一般的には、開部分集合と他の任意の集合とのミンコフスキー和は開部分集合になります。 ${\displaystyle \mathbb {K} ,}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {C} .}$${\displaystyle B_{r}:=\{s\in \mathbb {K} :|s|\leq r\}}$${\displaystyle r\in [0,\infty ]}$${\displaystyle 0}$${\displaystyle \mathbb {K} }$${\displaystyle r,s\in [0,\infty ],}$ ${\displaystyle B_{r}+B_{s}=B_{r+s}}$${\displaystyle cB_{r}=B_{|c|r}}$${\displaystyle c\in \mathbb {K} }$${\displaystyle |c|r}$${\displaystyle c\neq 0}$${\displaystyle r\neq \infty }$${\displaystyle r,s,}$${\displaystyle c}$${\displaystyle B_{r}}$${\displaystyle 0}$${\displaystyle 0}$

がのグラフであり、 が の-軸である場合、平面のこれら 2 つの閉部分集合のミンコフスキー和は、 -軸以外のすべてからなる開集合です。これは、2 つの閉集合のミンコフスキー和が必ずしも閉集合ではないことを示しています。ただし、2 つの閉部分集合のミンコフスキー和は、これらの集合の少なくとも 1 つがコンパクト部分集合でもある場合は、閉部分集合になります。 ${\displaystyle G=\{(x,1/x):0\neq x\in \mathbb {R} \}}$${\displaystyle f(x)={\frac {1}{x}}}$${\displaystyle Y=\{0\}\times \mathbb {R} }$${\displaystyle y}$${\displaystyle X=\mathbb {R} ^{2}}$ ${\displaystyle G+Y=\{(x,y)\in \mathbb {R} ^{2}:x\neq 0\}=\mathbb {R} ^{2}\setminus Y}$${\displaystyle y}$

ミンコフスキー加算は、次の命題で示されるように、 凸包を取る操作に関して適切に動作します。

実ベクトル空間のすべての空でない部分集合とに対して、それらのミンコフスキー和の凸包は、それらの凸包のミンコフスキー和である。${\displaystyle S_{1}}$${\displaystyle S_{2}}$

${\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}$

この結果は、空でない集合の有限集合に対してより一般的に当てはまります。

${\textstyle \operatorname {Conv} \left(\sum {S_{n}}\right)=\sum \operatorname {Conv} (S_{n}).}$

数学用語では、ミンコフスキー和と凸包形成の操作は可換操作である。^{[4] [5]}

が凸集合であればも凸集合である。さらに ${\displaystyle S}$${\displaystyle \mu S+\lambda S}$

${\displaystyle \mu S+\lambda S=(\mu +\lambda )S}$

任意の に対して成り立つ。逆に、この「分配法則」がすべての非負の実数 に対して成り立つ場合、集合は凸集合である。^[6]${\displaystyle \mu ,\lambda \geq 0}$${\displaystyle \mu ,\lambda }$

右の図は、非凸集合の例を示している。${\displaystyle A+A\subsetneq 2A.}$

次元の例は次のようになります。簡単に計算できますが、したがって再び${\displaystyle 1}$${\displaystyle B=[1,2]\cup [4,5].}$${\displaystyle 2B=[2,4]\cup [8,10]}$${\displaystyle B+B=[2,4]\cup [5,7]\cup [8,10],}$${\displaystyle B+B\subsetneq 2B.}$

ミンコフスキー和は2次元凸体の周長に線形に作用する。つまり、和の周長は周長の和に等しい。さらに、が一定幅の曲線（の内部）である場合、 のミンコフスキー和とその回転のミンコフスキー和は円板である。これら2つの事実を組み合わせると、一定幅の曲線の周長に関するバルビエの定理の簡単な証明が得られる。 ^[7]${\displaystyle K}$${\displaystyle K}$${\displaystyle 180^{\circ }}$

ミンコフスキー加算は数学的形態学において中心的な役割を果たしている。これは2Dコンピュータグラフィックスのブラシアンドストロークパラダイム（ Metafontのドナルド・E・クヌースによる使用などさまざまな用途がある）や3Dコンピュータグラフィックスのソリッドスイープ操作に見られる。また、地球移動距離、ひいては最適輸送と密接に関係していることも示されている。^[8]

ミンコフスキー和は、障害物間の物体の運動計画に使用されます。ミンコフスキー和は、物体のすべての許容位置の集合である配置空間の計算に使用されます。物体の位置がこの物体の固定点の位置によって一意に指定される平面内の物体の並進運動の単純なモデルでは、配置空間は、障害物の集合と原点に配置されて 180 度回転した可動物体のミンコフスキー和です。

数値制御加工では、NC ツールのプログラミングで、切削片とその軌跡のミンコフスキー和が材料の切削形状を与えるという事実を利用します。

OpenSCADでは、ミンコフスキー和を使用して、ある図形と別の図形の輪郭を描き、両方の図形の合成を作成します。

ミンコフスキー和は、集約される個々のオブジェクトが集合によって特徴付けられる場合の集約理論でも頻繁に使用されます。^{[9] [10]}

ミンコフスキー和、特にミンコフスキー差は、物理エンジンの凸包の衝突検出を計算するために、GJK アルゴリズムと併用されることがよくあります。

m 個とn個の頂点を持つ平面上の2 つの凸多角形 PとQについて、ミンコフスキー和は最大でm + n個の頂点を持つ凸多角形であり、次のように非公式に記述できる非常に簡単な手順で O( m + n ) の時間で計算できます。多角形の辺が与えられており、方向が多角形の境界に沿って、たとえば反時計回りであると仮定します。すると、凸多角形のこれらの辺が極角によって順序付けられていることが簡単にわかります。PとQからの有向辺の順序付けられたシーケンスを、 1 つの順序付けられたシーケンスSにマージします。これらの辺が、元の方向と平行を保ちながら自由に移動できる実線の矢印であると想像してください。次の矢印の末尾を前の矢印の先頭に接続することにより、シーケンスSの順序でこれらの矢印を組み立てます。結果として得られる多角形チェーンは、実際にはPとQのミンコフスキー和である凸多角形になります。

1 つの多角形が凸で、もう 1 つが凸でない場合、ミンコフスキー和の計算量は O( nm ) です。両方が凸でない場合、ミンコフスキー和の計算量は O(( mn ) ² )です。

ユークリッド空間の2つの部分集合の本質的なミンコフスキー和+ _eという概念もある。通常のミンコフスキー和は次のように書ける。

${\displaystyle A+B=\left\{z\in \mathbb {R} ^{n}\,|\,A\cap (z-B)\neq \emptyset \right\}.}$

したがって、本質的なミンコフスキー和は次のように定義される。

${\displaystyle A+_{\mathrm {e} }B=\left\{z\in \mathbb {R} ^{n}\,|\,\mu \left[A\cap (z-B)\right]>0\right\},}$

ここで、μはn次元ルベーグ測度を表す。「必須」という用語が使われる理由は、指示関数の次の性質による。

${\displaystyle 1_{A\,+\,B}(z)=\sup _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

それは次のことがわかる

${\displaystyle 1_{A\,+_{\mathrm {e} }\,B}(z)=\mathop {\mathrm {ess\,sup} } _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

ここで、「ess sup」は必須の上限を表します。

のKおよびLコンパクト凸集合に対して、ミンコフスキー和は凸集合の サポート関数によって記述できます。${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle h_{K+L}=h_{K}+h_{L}.}$

p ≥ 1の場合、Firey ^[11]は原点を含む コンパクト凸集合 Kと LのL ^pミンコフスキー和 K + _p Lを次のように定義しました。${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle h_{K+_{p}L}^{p}=h_{K}^{p}+h_{L}^{p}.}$

ミンコフスキーの不等式により、関数h _{K+ p L は}再び正同次かつ凸となり、したがってコンパクト凸集合のサポート関数となります。この定義は、L ^pブルン・ミンコフスキー理論の基本です。

• ブラシュケ和 – 2つの小さな多面体を組み合わせた多面体
• ブルン・ミンコフスキーの定理 – 幾何学における定理Pages displaying wikidata descriptions as a fallback、ミンコフスキー和の体積に関する不等式
• 畳み込み – ある関数が別の関数にシフトされる際の重なりの量を表す積分
• 膨張 – 数学的形態学における演算
• 浸食 – 数学的形態学における基本操作
• 区間演算 – 数値計算の誤差を制限する方法
• 混合体積（別名Quermassintegralまたは固有体積）
• 平行曲線 – 平行線の概念の一般化
• シャプレー・フォークマンの補題 – ベクトルの集合の和はほぼ凸である
• 和集合 – 2つの集合の要素のペアごとの和の集合
• 位相ベクトル空間#特性 – 近接性の概念を持つベクトル空間
• ゾノトープ – 超立方体から投影された凸多面体Pages displaying short descriptions of redirect targets

• アロー、ケネス J. ;ハーン、フランク H. (1980)。一般競争分析。経済学上級教科書。第 12 巻 ((1971) サンフランシスコ、カリフォルニア州: ホールデンデイ社。数学的経済学テキスト。 第6 版の再版)。アムステルダム: ノースホランド。ISBN 978-0-444-85497-1MR  0439057 。
• ガードナー、リチャード J. (2002)、「ブルン・ミンコフスキー不等式」、Bull. Amer. Math. Soc. (NS)、39 (3): 355–405 (電子版)、doi : 10.1090/S0273-0979-02-00941-2
• グリーン、ジェリー、ヘラー、ウォルター P. (1981) 「1 数学的解析と凸性と経済学への応用」 アロー、ケネス ジョセフ、イントリリゲーター、マイケル D (編)数理経済学ハンドブック、第 1巻.経済学ハンドブック。第1巻。アムステルダム：ノースホランド出版社。pp. 15–52。doi ：10.1016/S1573-4382（81）01005-9。ISBN 978-0-444-86126-9. MR  0634800。
• ヘンリー・マン（1976年）『加法定理：群論と数論の加法定理』（1965年ワイリー版の訂正再版）、ハンティントン、ニューヨーク：ロバート・E・クリーガー出版社、ISBN 978-0-88275-418-5– www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html より
• Rockafellar, R. Tyrrell (1997)。凸解析。プリンストン数学のランドマーク（1979年プリンストン数学シリーズ 第28版の再版 ）。プリンストン、ニュージャージー：プリンストン大学出版局。pp. xviii+ 451。ISBN 978-0-691-01586-6. MR  1451876。
• ネイサンソン、メルヴィン B. (1996)、加法数論：逆問題と和集合の幾何学、GTM、第 165 巻、Springer、Zbl  0859.11003。
• Oks, Eduard; Sharir, Micha (2006)、「単調多角形と一般単純多角形のミンコフスキー和」、離散および計算幾何学、35 (2): 223–240、doi : 10.1007/s00454-005-1206-y。
• シュナイダー、ロルフ（1993）、凸体：ブルン・ミンコフスキー理論、ケンブリッジ：ケンブリッジ大学出版局。
• タオ、テレンス & ヴー、ヴァン (2006)、加法組合せ論、ケンブリッジ大学出版局。
• Mayer, A.; Zelenyuk, V. (2014). 「リソースの再配分を可能にするマルムキスト生産性指標の集約」。European Journal of Operational Research . 238 (3): 774–785. doi :10.1016/j.ejor.2014.04.003.
• Zelenyuk, V (2015). 「規模の効率性の集約」.ヨーロッパオペレーションズリサーチジャーナル. 240 (1): 269–277. doi :10.1016/j.ejor.2014.06.038.

• 「ミンコフスキー加算」、数学百科事典、EMS Press、2001 [1994]
• ハウ、ロジャー（1979）、集合のベクトル和の凸性傾向について、カウルズ財団ディスカッションペーパー、第538巻、カウルズ経済研究財団、イェール大学
• ミンコフスキー和、計算幾何学アルゴリズムライブラリ
• 「2 つの三角形のミンコフスキー和」および「円板と多角形のミンコフスキー和」、George Beck、Wolfram デモンストレーション プロジェクト。
• アレクサンダー・ボゴモーリニーによるミンコフスキーの凸形状の加法: アプレット
• Wikibooks:OpenSCAD ユーザーマニュアル/変換#minkowski by Marius Kintel: アプリケーション
• ミンコフスキー加法のロボット工学への応用 (Joan Gerard 著)
• ミンコフスキー加法性、凸単調性、およびアースムーバー距離のその他の特性の実証