ミンコフスキー加算

赤い図は青い図と緑の図のミンコフスキー和です。

数学では(加法的な)アーベル群の2つの部分集合ABの和集合は、 Aの各要素をBの各要素に追加することによって形成されます

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

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

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

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

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

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

ミンコフスキー和A + B

例えば、2つの集合AB があり、それぞれが の2つの三角形頂点を表す3つの位置ベクトル(非公式には3つの点)で構成され座標が

そして

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

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

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

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

別の例として、実数または複素数である体における開球または閉球のミンコフスキー和を考えてみましょう。がにおいてを中心とする半径 の閉球である場合、任意の に対してまた はが定義されるような任意のスカラーに対して成り立ちます(または のときに起こります)。、、および がすべてゼロでない場合、 が 0 を中心とする閉球ではなく開球として定義された場合でも、同じ等式が成り立ちます (半径 0 の開球は空集合であるため、ゼロでないという仮定が必要です)。閉球と開球のミンコフスキー和は開球です。より一般的には、開部分集合との任意の集合とのミンコフスキー和は開部分集合になります。

が のグラフあり、 が の-軸である場合、平面上のこれら2つの閉部分集合のミンコフスキー和は、 -軸以外のすべてからなる開集合となる。これは、2つの閉集合のミンコフスキー和が必ずしも閉集合になるとは限らないことを示す。しかし、2つの閉部分集合のミンコフスキー和は、これらの集合の少なくとも1つがコンパクト部分集合でもある場合、閉部分集合となる。

ミンコフスキー和の凸包

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

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

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

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

が凸集合ならばも凸集合である。さらに

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

非凸集合の例としては、

右の図は、非凸集合の例を示しており、

1次元の例は次のようになります。簡単に計算できますが、したがって、

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

アプリケーション

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

モーションプランニング

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

数値制御(NC)加工

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

3Dソリッドモデリング

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

集約理論

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

衝突検出

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

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

4 つの線分のミンコフスキー加法。左側のペインには、2 行 2 列の配列で 4 つの集合が表示されます。各集合には、赤で表示された 2 つの点が含まれます。各集合では、2 つの点はピンク色の線分で結ばれており、これが元の集合の凸包です。各集合には、プラス記号で示される 1 つの点が含まれます。2 行 2 列の配列の上段では、プラス記号は線分の内側にあり、下段では、プラス記号は赤い点の 1 つと一致します。これで、図の左側のペインの説明は完了です。右側のペインには、集合のミンコフスキー和が表示されます。これは、各加数集合から 1 つの点だけを含む和の和の和和の和集合です。表示されている集合では、16 個の和はそれぞれ異なる点であり、赤で表示されます。右側の赤い和点は、左側の赤い加数点の和です。 16個の赤い点の凸包はピンク色で塗られています。右側の和集合のピンク色の内部には、ちょうど1つのプラス記号があり、これは右側のプラス記号の(唯一の)和です。右側のプラス記号は、左側の集合の4つのプラス記号の和であり、元の非凸加群から正確に2点、残りの加群の凸包から正確に2点です。
ミンコフスキー加法と凸包。16個の濃い赤色の点(右側)は、4つの非凸集合(左側)のミンコフスキー和を形成します。各非凸集合は、2つの赤色の点で構成されています。それらの凸包(​​ピンク色の部分)にはプラス記号(+)が含まれています。右側のプラス記号は、左側のプラス記号の和です。

平面ケース

平面上の2つの凸多角形

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

他の

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

必須ミンコフスキー和

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

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

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

それは次のことがわかる

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

L pミンコフスキー和

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

p ≥ 1の場合、Firey [11]は原点を含むコンパクト凸集合KLのL pミンコフスキー和 K + p Lを次のように定義しました。

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

参照

注記

  1. ^ Hadwiger, Hugo (1950)、「Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt」、Mathematische Zeitschrift53 (3): 210–218doi :10.1007/BF01175656、S2CID  121604732 2023-01-12 に取得
  2. ^ Li, Wei (2011年秋). GPUベースのボクセル化ミンコフスキー和の計算とその応用 (博士号).カリフォルニア大学バークレー校. pp.  13– 14. 2023年1月10日閲覧
  3. ^ ロザノ・ペレス, トマス (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日閲覧.
  4. ^ 定理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.
  5. ^ミンコフスキー加法と 凸化の可換性については、シュナイダーの定理1.1.2(2~3ページ)を参照。この参考文献では、ミンコフスキー和集合の凸包に関する多くの文献が「第3章 ミンコフスキー加法」(126~196ページ)で議論されている。シュナイダー、ロルフ(1993年)。凸体:ブルン・ミンコフスキー理論。数学とその応用百科事典。第44巻。ケンブリッジ:ケンブリッジ大学出版局。pp. xiv+490。ISBN 978-0-521-35220-8. MR  1216521。
  6. ^ 第1章:シュナイダー、ロルフ(1993年)凸体:ブルン・ミンコフスキー理論。数学とその応用百科事典第44巻。ケンブリッジ:ケンブリッジ大学出版局。pp. xiv+ 490。ISBN 978-0-521-35220-8. MR  1216521。
  7. ^ cut-the-knotにおけるバルビエの定理 (Java)
  8. ^ Kline, Jeffery (2019). 「d次元地球移動問題の特性」.離散応用数学. 265 : 128–141 . doi : 10.1016/j.dam.2019.02.042 . S2CID  127962240.
  9. ^ Zelenyuk, V. (2015). 「規模の効率性の集約」 .ヨーロッパオペレーションズリサーチジャーナル. 240 (1): 269– 277. doi :10.1016/j.ejor.2014.06.038.
  10. ^ Mayer, A.; Zelenyuk, V. (2014). 「資源の再配分を可能にするマルムキスト生産性指標の集約」 . European Journal of Operational Research . 238 (3): 774– 785. doi :10.1016/j.ejor.2014.04.003.
  11. ^ Firey, William J. (1962)、「凸体のp平均」、 Mathematica Scandinavica10 : 17–24doi : 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Minkowski_addition&oldid=1318411333"