ミンコフスキー加算

数学では、（加法的な）アーベル群の2つの部分集合 $A$ と $Bの和集合は、$ $Aの各要素を$ $B$ の各要素に追加することによって形成されます。 $A+B=\{a+b\mid a\in A,\ b\in B\}.$

幾何学において、ユークリッド空間の二つの部分集合 $A$ と $Bの$ ミンコフスキー和は、位置ベクトルが $A$ と $B$ の位置ベクトルの和集合を形成するような点の集合である。ミンコフスキー和はユークリッド空間における原点の選択に依存する。原点の変更はミンコフスキー和の移動に相当するため、ミンコフスキー和は移動を除けば定義され、その形状と向きは明確に定義される。

ミンコフスキー差（ミンコフスキー減算、ミンコフスキー分解、あるいは幾何差とも呼ばれる）^[1]は、対応する逆関数であり、Bと和をとることでAを復元できる集合を生成する。これは、 Aの補集合とBを原点を中心とした鏡映関係にミンコフスキー和を足し合わせた補集合として定義される。^[2] ${\textstyle (A-B)}$

${\begin{aligned}-B&=\{\mathbf {-b} \,|\,\mathbf {b} \in B\}\\A-B&=(A^{\complement }+(-B))^{\complement }\end{aligned}}$

この定義により、ミンコフスキー和と差の間に対称的な関係が成立する。B との和と差を交互に取ることは必ずしも等価ではないことに注意されたい。和は差では再び開くことができない隙間を埋めることができ、差は和では再現できない小さな島を消し去ることができる。

${\begin{aligned}(A-B)+B&\subseteq A\\(A+B)-B&\supseteq A\\A-B&=(A^{\complement }+(-B))^{\complement }\\A+B&=(A^{\complement }-(-B))^{\complement }\\\end{aligned}}$

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

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

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

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

例

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

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

そして

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

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

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

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

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

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

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

$S+\emptyset =\emptyset .$

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

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

ミンコフスキー和の凸包

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

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

{\textstyle S_{1}}

{\textstyle S_{2}}

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

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

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

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

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

$\mu S+\lambda S=(\mu +\lambda )S$

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

右の図は、非凸集合の例を示しており、 ${\textstyle 2A\subsetneq A+A.}$

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

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

アプリケーション

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

モーションプランニング

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

数値制御（NC）加工

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

3Dソリッドモデリング

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

集約理論

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

衝突検出

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

ミンコフスキー和を計算するアルゴリズム

平面ケース

平面上の2つの凸多角形

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

他の

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

必須ミンコフスキー和

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

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

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

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

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

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

それは次のことがわかる

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

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

L ^pミンコフスキー和

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

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

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

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

ミンコフスキー不等式により、関数h _{K+ _p L は}再び正同次かつ凸であり、したがってコンパクト凸集合の支持関数となる。この定義は、L ^pブルン＝ミンコフスキー理論において基本的なものである。

参照

ブラシュケ和 – 2つの小さな多面体を組み合わせた多面体
ブルン・ミンコフスキーの定理 – 幾何学における定理、ミンコフスキー和の体積に関する不等式
畳み込み – ある関数を別の関数の上に重ねたときの重なりの量を表す積分
膨張 – 数学的形態学における演算
浸食 – 数学的形態学における基本演算
区間演算 – 数値計算の誤差を制限する方法
混合容積（別名：Quermassintegralまたは固有容積）
平行曲線 – 平行線の概念の一般化
シャプレー・フォークマンの補題 – ベクトルの集合の和はほぼ凸である
Sumset – A の各ベクトルに B の各ベクトルを加算してベクトルセット A と B を合計します。
位相ベクトル空間#性質 – 近接性の概念を持つベクトル空間
ゾノトープ – 超立方体から投影された凸多面体

注記

^ Hadwiger, Hugo (1950)、「Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt」、Mathematische Zeitschrift、53 (3): 210–218、doi :10.1007/BF01175656、S2CID 121604732 、2023-01-12 に取得
^ Li, Wei (2011年秋). GPUベースのボクセル化ミンコフスキー和の計算とその応用 (博士号).カリフォルニア大学バークレー校. pp. 13– 14. 2023年1月10日閲覧。
^ ロザノ・ペレス, トマス (1983年2月). 「空間計画：構成空間アプローチ」(PDF) . IEEE Transactions on Computers . C-32 (2): 111. doi :10.1109/TC.1983.1676196. hdl :1721.1/5684. S2CID 18978404. 2023年1月10日閲覧.
^ 定理3（562–563ページ）：Krein, M. ; Šmulian, V. (1940). 「バナッハ空間に共役な空間内の規則凸集合について」Annals of Mathematics . Second Series. 41 (3): 556– 583. doi :10.2307/1968735. JSTOR 1968735. MR 0002009.
^ミンコフスキー加法と 凸化の可換性については、シュナイダーの定理1.1.2（2～3ページ）を参照。この参考文献では、ミンコフスキー和集合の凸包に関する多くの文献が「第3章ミンコフスキー加法」（126～196ページ）で議論されている。シュナイダー、ロルフ（1993年）。凸体：ブルン・ミンコフスキー理論。数学とその応用百科事典。第44巻。ケンブリッジ：ケンブリッジ大学出版局。pp. xiv+490。ISBN 978-0-521-35220-8. MR 1216521。
^ 第1章：シュナイダー、ロルフ（1993年）凸体：ブルン・ミンコフスキー理論。数学とその応用百科事典第44巻。ケンブリッジ：ケンブリッジ大学出版局。pp. xiv+ 490。ISBN 978-0-521-35220-8. MR 1216521。
^ cut-the-knotにおけるバルビエの定理 (Java) 。
^ Kline, Jeffery (2019). 「d次元地球移動問題の特性」.離散応用数学. 265 : 128–141 . doi : 10.1016/j.dam.2019.02.042 . S2CID 127962240.
^ Zelenyuk, V. (2015). 「規模の効率性の集約」 .ヨーロッパオペレーションズリサーチジャーナル. 240 (1): 269– 277. doi :10.1016/j.ejor.2014.06.038.
^ Mayer, A.; Zelenyuk, V. (2014). 「資源の再配分を可能にするマルムキスト生産性指標の集約」 . European Journal of Operational Research . 238 (3): 774– 785. doi :10.1016/j.ejor.2014.04.003.
^ Firey, William J. (1962)、「凸体のp平均」、 Mathematica Scandinavica、10 : 17–24、doi : 10.7146/math.scand.a-10510

参考文献

アロー、ケネス・J.、ハーン、フランク・H. (1980).一般競争分析. 経済学上級教科書. 第12巻（1971年サンフランシスコ、カリフォルニア州：ホールデン・デイ社発行『数理経済学テキスト』第6 版の再版）. アムステルダム、ノースホランド. ISBN 978-0-444-85497-1. MR 0439057。
ガードナー, リチャード J. (2002)、「ブルン・ミンコフスキー不等式」、アメリカ数学会誌 (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より
ロッカフェラー、R. ティレル(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プレス、2001 [1994]
ハウ、ロジャー（1979）「集合のベクトル和の凸性への傾向について」、カウルズ財団ディスカッションペーパー、第538巻、カウルズ経済研究財団、イェール大学
ミンコフスキー和、計算幾何学アルゴリズムライブラリ
「2 つの三角形のミンコフスキー和」および「円板と多角形のミンコフスキー和」、George Beck、The Wolfram Demonstrations Project 著。
アレクサンダー・ボゴモーリニーによるミンコフスキーの凸図形の加法：アプレット
Wikibooks:OpenSCAD ユーザーマニュアル/変換#minkowski by Marius Kintel: アプリケーション
ミンコフスキー加法のロボット工学への応用（ジョアン・ジェラード著）
ミンコフスキー加法性、凸単調性、およびアースムーバー距離のその他の特性の実証