민코프스키 덧셈 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Сумма Минковского.svg|섬네일|alt=|빨간 도형은 파란 도형과 초록색 도형의 민코프스키 덧셈이다.]]

[[기하학]]에서, [[유클리드 공간]]의 [[위치벡터]] ''A''와 ''B''의 두 [[집합]]의 '''민코프스키 합'''([[팽창 (형태학)|팽창]]이라고도 알려져 있다)은 ''A''에 있는 모든 벡터를 ''B''에 있는 각각의 벡터에 더해서 만들어진다. 이는 다음과 같다:

: <math>A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.</math>

유사하게, '''민코프스키 차'''(또는 기하학적 차)<ref>{{인용|last=Hadwiger|first=Hugo|title=Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt|journal=Math.Z.|volume=53|issue=3 |pages=210–218 |year=1950}}</ref>는 다음과 같이 정의된다:
: <math>A - B = \{\mathbf{c}\,|\,\mathbf{c}+B\subseteq A\}.</math>

일반적으로 <math>A - B\ne A+(-B)</math>인 것은 중요하다. 예를 들어, 일차원 경우 <math>A =[-2,2]</math>와 <math>B =[-1,1]</math>일 때, 민코프스키 차는 <math>A-B=[-1,1]</math>이지만 <math>A+(-B)=A+B=[-3,3]</math>이다. 민코프스키 합과 차를 연결하는 올바른 공식은 다음과 같다 (여기에서 <math>X^c</math>는 <math>X</math>의 여집합을 의미한다):
: <math>A - B = (A^c+(-B))^c.</math>

이차원의 경우에서, 민코프스키 차는 [[디지털 화상 처리|이미지 처리]]에서 [[침식 (형태학)]]과 긴밀하게 연관이 있다.

[[파일:Minkowski-sumex4.svg|섬네일|민코프스키 합 {{math|''A'' + ''B''}}]]
[[파일:Minkowski-sumex2.svg|섬네일|''B'']]
[[파일:Minkowski-sumex1.svg|섬네일|''A'']]

이 개념은 [[헤르만 민코프스키]]의 이름을 붙였다.

== 예시 ==
예를 들어, <math>\mathbb{R}^2</math>에서 두 개의 [[삼각형]]을 나타내는 [[꼭짓점]]인 다음 세 개의 위치벡터(비공식적, 세 점)로 이루어진 두 집합 ''A''와 ''B''를 가지고있다고 가정하자:

:<math>A = \{(1,0), (0,1), (0,-1)\}</math>

:<math>B = \{(0,0), (1,1), (1,-1)\},</math>

그러면 그 민코프스키 합은 다음과 같다:

:<math>A + B = \{(1,0), (2,1), (2,-1), (0,1), (1,2), (0,-1), (1,-2)\},</math>

육각형의 꼭짓점을 이룬다.

민코프스키 덧셈에서, [[영벡터]] 0만을 포함하는 ''영집합'' {0}은 [[항등원]]이다: 벡터 공간의 모든 부분집합 ''S''에 대해서 다음이 성립한다:
:<math>S + \{0\} = S.</math>

[[공집합]]은 공집합은 다른 모든 부분집합을 없애기 때문에 민코프스키 덧셈에서 중요하다: 벡터 공간의 모든 부분집합 ''S''에 대해서, 공집합과의 합은 공집합이다:
:<math>S + \emptyset = \emptyset.</math>

[[파일:Extreme points.svg|섬네일|오른쪽|alt=토르티야 칩이나 삼각형 표지판처럼 매끈한 삼각형의 그림. 세 둥근 코너는 빨간 곡선으로 그려져 있다. 삼각형의 나머지 내부는 파란 색으로 칠해져 있다.|빨간 집합의 [[볼록 폐포]]에서, 각각의 파란 점은 어떤 빨간 점의 [[볼록 조합]]이다.]]

[[파일:Minkowski sum graph - vector version.svg|섬네일|alt=세 개의 정사각형이 데카르트 좌표의 제 1사분면에 나타나 있다. 정사각형 Q<sub>1</sub>={{closed-closed|0,1}}×{{closed-closed|0,1}}은 초록색이다. 정사각형 Q<sub>2</sub>={{closed-closed|1,2}}×{{closed-closed|1,2}}은 갈색이고, 청록색 정사각형 Q<sub>1</sub>+Q<sub>2</sub>={{closed-closed|1,3}}×{{closed-closed|1,3}}의 안에 있다.|집합의 '''민코프스키 덧셈'''. 정사각형 ''Q''<sub>1</sub>={{closed-closed|0,1}}<sup>2</sup>과 ''Q''<sub>2</sub>={{closed-closed|1,2}}<sup>2</sup>의 덧셈은 정사각형 ''Q''<sub>1</sub>+''Q''<sub>2</sub>={{closed-closed|1,3}}<sup>2</sup>이다.]]

== 민코프스키 덧셈의 볼록 폐포 ==
민코프스키 덧셈은 [[볼록 폐포]]를 취하는 연산에 대해서 다음의 명제에서 보인 것 같이 잘 동작한다:
* 실 벡터 공간의 어떤 진부분집합 ''S''<sub>1</sub>와 ''S''<sub>2</sub>에 대해서, 그 민코프스키 덧셈의 볼록 폐포는 그 볼록 폐포의 민코프스키 덧셈이다:
:: <math>\operatorname{Conv}(S_1 + S_2) = \operatorname{Conv}(S_1) + \operatorname{Conv}(S_2).</math>
이 결과는 더 일반적으로 모든 유한한 공집합이 아닌 집합의 집합에 대해서도 적용된다:
:<math>\operatorname{Conv}\left(\sum{S_n}\right) = \sum\operatorname{Conv}(S_n).</math>

수학 용어학에서, 민코프스키 덧셈과 [[볼록 폐포]]를 만드는 [[연산]]은 [[가환]] 연산이다.<ref>Theorem&nbsp;3 (pages&nbsp;562–563): {{뉴스 인용|first1=M.|last1=Krein|authorlink1=Mark Krein|first2=V.|last2=Šmulian|year=1940|title=On regularly convex sets in the space conjugate to a Banach space|journal=Annals of Mathematics&nbsp;(2), Second series|volume=41|pages=556–583|doi=10.2307/1968735|mr=2009 | jstor = 1968735}}</ref><ref>민코프스키 덧셈과 [[볼록 폐포|볼록 폐포화]]의 가환성에 대해서는, Schneider에서 Theorem&nbsp;1.1.2 (pages&nbsp;2–3)를 보라; 이 참고 문헌은 민코프스키 [[덧셈집합]]의 [[볼록 폐포]]에 대한 문헌들을 "Chapter&nbsp;3 Minkowski addition" (pages&nbsp;126–196)에서 논의한다: {{서적 인용|title=Convex bodies: The Brunn–Minkowski theory|last=Schneider|first=Rolf|year=1993|series=Encyclopedia of mathematics and its applications|volume=44|publisher=Cambridge&nbsp;University Press|location=Cambridge|pages=xiv+490|isbn=0-521-35220-7|mr=1216521}}</ref>

{{mvar|S}}가 볼록 집합이라면 <math>\mu S+\lambda S</math>는 볼록 집합이다; 게다가 모든 <math>\mu,\lambda \geq 0</math>에 대해서 다음이 성립한다:
:<math>\mu S+\lambda S=(\mu+\lambda)S</math>
반대로, 음이 아닌 어떤 실수 <math>\mu, \lambda</math>에 대해서 이 "[[분배법칙]]"이 적용되면 집합은 볼록이다.<ref>Chapter 1: {{서적 인용|last=Schneider|first=Rolf|title=Convex bodies: The Brunn–Minkowski theory|series=Encyclopedia of mathematics and its applications|volume=44|publisher=Cambridge&nbsp;University Press|location=Cambridge|year=1993|pages=xiv+490 |isbn=0-521-35220-7|mr=1216521}}</ref>

그림은 {{math|''A'' + ''A'' ⊋ 2''A''}}인 비볼록 집합의 예시를 보여준다<!-- don't use <math> for that due to broken spacing in HTML -->.
[[파일:Minkowskisum.svg|섬네일|{{math|''A'' + ''A'' ≠ 2''A''}}인 비볼록 집합의 예시]] 1차원의 예시: ''B''=[1,2]∪[4,5]. 이것은 쉽게 2''B''=[2,4]∪[8,10]이지만 ''B''+''B''=[2,4]∪[5,7]∪[8,10]인 것을 계산할 수 있다. 따라서, 역시 {{math|''B''+''B'' ⊋ 2''B''}}이다.

민코프스키 덧셈은 이차원 볼록체의 둘레에서 선형적으로 작용한다: 덧셈의 둘레는 둘레의 합과 같다. 게다가, ''K''가 [[정폭도형]](의 내부)이면, ''K''와 그것을 180°돌린 도형의 민코프스키 덧셈은 원판이다. 이 두 사실을 결합하면 정폭도형의 둘레에서 [[바르비에의 정리]]의 간략하게 증명할 수 있다.<ref>[http://www.cut-the-knot.org/ctk/Barbier.shtml The Theorem of Barbier (Java)] at [[cut-the-knot]].</ref>

== 적용 ==
민코프스키 덧셈은 [[수학적 형태학]]에서 중요한 역할을 한다. 이것은 [[2차원 컴퓨터 그래픽스]](의 다양한 사용과 [[메타 폰트]]에서 [[도널드 커누스]]에 의한 저명성과 함께)의 [[brush-and-stroke paradigm]]과[[3차원 컴퓨터 그래픽스]]의 [[솔리드 스윕]] 연산에서 드러난다.

=== 모션 계획 ===
민코프스키 덧셈은 장애물 사이로 지나는 [[모션 계획]]에서 사용된다. 이것은 물체의 모든 허용 가능한 집합인 [[짜임새 공간 (물리)|짜임새 공간]]의 계산에 사용된다. 물체의 위치가 이 물체의 고정점에 의해서 유일하게 결정되는 평면에서 물체의 평행이동 모션의 가장 단순한 모델에서, 짜임새 공간은 장애물의 집합과 움직이는 물체를 원점에 둬서 180도 돌린 것의 민코프스키 덧셈이다.

=== 수치 제어 (NC) 가공 ===
[[수치 제어]] 가공에서, NC 툴의 프로그래밍은 [[깎는 조각]]과 그 궤적의 민코프스키 덧셈은 물체에서 깎는 모양을 준다는 사실을 이용한다.

=== 3d 솔리드 모델링 ===
오픈SCAD에서 민코프스키 덧셈은 한 도형과 두 도형의 복합체를 만드는 다른 도형의 윤곽선을 그릴 때 이용된다.

=== 집계 이론 ===
민코프스키 덧셈은 집계 이론에서 집계된 각각의 물체가 집합으로 특정될 경우에 종종 사용된다.<ref>[https://ideas.repec.org/a/eee/ejores/v240y2015i1p269-277.html Zelenyuk, V. (2015) "Aggregation of scale efficiency," European Journal of Operational Research, 240:1, pp 269-277.]</ref><ref>[https://ideas.repec.org/a/eee/ejores/v238y2014i3p774-785.html Mayer, A. and Zelenyuk, V. (2014) "Aggregation of Malmquist productivity indexes allowing for reallocation of resources," European Journal of Operational Research, 238:3, pp 774-785]</ref>

== 민코프스키 덧셈을 계산하는 알고리즘 ==
[[파일:Shapley–Folkman lemma.svg|섬네일|300px|alt=선분 네 개의 민코프스키 덧셈. 왼쪽 창에는 네 개의 집합을 2 x 2 배열로 나타냈다. 각각의 집합은 정확히 빨간색으로 표시된 점이 두 개가 있다. 각 집합에서, 두 점은 원래 집합의 볼록 폐포인 핑크색 선분으로 연결되어 있다. 각각의 집합은 더하기 기호로 표시된 한 점을 가진다. 2 x 2 배열의 윗줄에서, 더하기 기호는 선분의 내부에 위치한다; 아랫줄에서, 더하기 기호는 빨간 점과 일치한다. 이것은 다이어그램의 왼쪽 창의 설명이다. 오른쪽 창은 각갹의 더해지는 집합의 정확히 한 점을 가지는 덧셈의 합집합인 집합의 민코프스키 덧셈을 나타낸다; 나타낸 집합에서, 덧셈 16개는 빨간 색으로 나타낸 구분된 점이다: 오른쪽의 빨간 덧셈 점은 왼쪽의 빨간 더해지는 점의 덧셈이다. 빨간 점 16개의 볼록 폐포는 분홍색으로 칠해졌다. 오른쪽에서 더하기 기호의 (유일한) 덧셈인 더하기 기호가 오른쪽 덧셈집합의 분홓색 내부에 있다. 오른쪽 더하기 기호는 당연히 왼쪽 집합에서 더하기 기호 네 개의 덧셈이다, 정확히는 원래의 비볼록인 더하는 집합의 두 점과 나머지 더하는 집합의 볼록 폐포의 두 점의 덧셈이다.|민코프스키 덧셈과 볼록 폐포. 빨간 점의 쌍으로 이루어진 (왼쪽에 있는) 비볼록 집합 네 개의 덧셈으로 생긴 (오른쪽에 있는) 16개의 진한 빨간색 점. (분홍색으로 칠해진) 볼록 폐포는 더하기 기호 (+)를 포함한다: 오른쪽 더하기 기호는 왼쪽 더하기 기호의 덧셈이다.]]

=== 평면의 경우 ===

==== 평면의 볼록 다각형 두 개 ====
꼭짓점이 각각 m개와 n개인 평면의 [[볼록 다각형]] P와 Q에 대해서, 그 민코프스키 합은 최대 m + n개의 꼭짓점이 있는 볼록 다각형이고 비공식적인 다음의 매우 간단한 단계로 시간 O (m + n)에 계산할 수 있다. 다각형의 모서리와 다각형 경계의 방향 (말하자면 반시계 방향 같은)이 주어졌다고 가정하자. 그러면 쉽게 이 볼록 다각형의 변이 [[극좌표|중심각]] 순서대로 있다는 것을 볼 수 있다. 정렬된 유향 변의 수열 P와 Q를 하나의 정렬된 수열 S으로 [[병합 알고리즘|병합]]하자. 이 변들이 원래 방향에 평행하게 유지하면서 자유롭게 움직일 수 있는 고체 [[화살표]]라고 생각하자. 화살표들을 다음 화살표의 꼬리를 이전 화살표의 머리에 붙여서 수열 S의 순서대로 조합하자. 이 결과로 나오는 [[다각형 체인]]이 사실은 P와 Q의 민코프스키 합인 볼록 다각형이라는 것을 알 수 있다.

==== 기타 ====
한 다각형이 볼록이고 다른 것은 아니라면, 그 민코프스키 덧셈의 완비성은 O(nm)이다. 둘 다 비볼록이라면, 그 민코프스키 덧셈의 완비성은 O((mn)<sup>2</sup>)이다.

== 본질적 민코프스키 덧셈 ==
유클리드 공간의 두 부분집합의 '''본질적 민코프스키 덧셈'''의 표기 +<sub>e</sub>가 있다. 일반적인 민코프스키 덧셈은 다음과 같이 적는다는 것을 주목하자:

:<math>A + B = \{ z \in \mathbb{R}^{n} \,|\, A \cap (\{z\} - B) \neq \emptyset \}.</math>

따라서, '''본질적 민코프스키 덧셈'''은 다음과 같이 정의된다:

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

여기서 ''μ''는 ''n''-차원 [[르베그 측도]]를 의미한다. "본질적"이라는 용어를 쓰는 이유는 [[지시 함수]]의 다음 특성 때문이다: 다음일 때

:<math>1_{A \,+\, B} (z) = \sup_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x)</math>

다음을 볼 수 있다:

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

여기서 "ess sup"는 [[본질적 상한]]을 의미한다.

== ''L<sup>p</sup>'' 민코프스키 덧셈 ==

<math>\mathbb{R}^n</math>의 콤팩트 볼록 집합 ''K''와 ''L''에 대해서, 민코프스키 합은 볼록 집합의 [[지지 함수]]로 설명될 수 있다:
:<math> h_{K+L} = h_K + h_L. </math>
''p ≥ 1''일 때, Firey<ref>{{인용|last=Firey|first=William J.|title=''p''-means of convex bodies|journal=Math. Scand.|volume=10|pages=17-24|year=1962}}</ref>는 '''L<sup>p</sup> 민코프스키 합'''을 원점을 다음과 같이 포함하는 <math>\mathbb{R}^n</math>에 있는 콤팩트 볼록 집합 ''K''와 ''L''의 ''K+<sub>p</sub>L''로 정의했다:
:<math> h_{K +_p L}^p = h_K^p + h_L^p.</math>
[[민코프스키 부등식]]에 의해서, 함수 ''h<sub>K+<sub>p</sub>L</sub>''은 다시 양의 동차이고 볼록이고 따라서 콤팩트 볼록 함수의 지지 함수이다. 이 정의는 ''L''<sup>p</sup> Brunn-Minkowski theory에서 근본적이다.

== 같이 보기 ==
* [[팽창 (형태학)|팽창]]
* [[침식 (형태학)|침식]]
* [[구간 산술]]
* [[혼합 부피]] (a.k.a. [[Quermassintegral]] 또는 [[intrinsic volume]])
* [[평행 곡선]]
* [[섀플리-포크먼 보조정리]]
* [[Zonotope]]
* [[합성곱]]

== 참조 ==
<references/>

* {{서적 인용|last1=Arrow|first1=Kenneth&nbsp;J.|authorlink1=Kenneth Arrow|last2=Hahn|first2=Frank&nbsp;H.|authorlink2=Frank Hahn|year=1980<!-- |chapter=Appendix&nbsp;B: Convex and related sets -->|title=General competitive analysis|publisher=North-Holland|<!-- pages=375–401 -->|series=Advanced textbooks in economics|volume=12|edition=reprint of (1971)  San&nbsp;Francisco,&nbsp;CA: Holden-Day,&nbsp;Inc. Mathematical economics texts.&nbsp;'''6'''|location=Amsterdam|isbn=0-444-85497-5|mr=439057|ref=harv}}
* {{인용 |last=Gardner |first=Richard J. |title=The Brunn-Minkowski inequality |journal=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]] (N.S.) | volume=39 | issue=3 | year=2002 | pages=355–405 (electronic) | doi=10.1090/S0273-0979-02-00941-2 }}
* {{서적 인용|first1=Jerry|last1=Green|first2=Walter&nbsp;P.|last2=Heller|chapter=1 Mathematical&nbsp;analysis and&nbsp;convexity with applications to economics|pages=15–52|url=http://www.sciencedirect.com/science/article/B7P5Y-4FDF0FN-5/2/613440787037f7f62d65a05172503737|doi=10.1016/S1573-4382(81)01005-9|title=Handbook of mathematical&nbsp;economics, Volume&nbsp;'''I'''|editor1-link=Kenneth Arrow|editor1-first=Kenneth&nbsp;Joseph|editor1-last=Arrow|editor2-first=Michael&nbsp;D<!-- . -->|editor2-last=Intriligator|series=Handbooks in economics|volume=1|publisher=North-Holland Publishing&nbsp;Co|location=Amsterdam|year=1981|isbn=0-444-86126-2|mr=634800|ref=harv|확인날짜=2017-11-22|보존url=https://archive.today/20121217191748/http://www.sciencedirect.com/science/article/pii/S1573438281010059|보존날짜=2012-12-17|url-status=dead}}
* {{인용
|author=Henry Mann |authorlink=Henry Mann
|title=Addition Theorems: The Addition Theorems of Group Theory and Number Theory
|publisher=Robert E. Krieger Publishing Company
|via=http://www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html
|location=Huntington, New York
|year=1976
|edition=Corrected reprint of 1965 Wiley
|isbn=0-88275-418-1
}}
* {{서적 인용|last=Rockafellar|first=R.&nbsp;Tyrrell|authorlink=R. Tyrrell Rockafellar|title=Convex analysis|edition=Reprint of the 1979 Princeton mathematical series&nbsp;'''28'''|series=Princeton landmarks in mathematics|publisher=Princeton University Press|location=Princeton, NJ|year=1997|pages=xviii+451|isbn=0-691-01586-4|mr=1451876|<!-- Rockafellar, the "bible" of convex analysis, according to Lemaréchal and Hiart-Urruty, gets two MRs because it's the best-->id={{MR|274683}}|ref=harv}}
* {{인용 |first=Melvyn B. |last=Nathanson |title=Additive Number Theory: Inverse Problems and Geometry of Sumsets |series=GTM |volume=165 |publisher=Springer |year=1996 |zbl=0859.11003 }}.
* {{인용 |last=Oks |first=Eduard |last2=Sharir |first2=Micha |year=2006 |title=Minkowski Sums of Monotone and General Simple Polygons |journal=Discrete and Computational Geometry |volume=35 |issue=2 |pages=223–240 |doi=10.1007/s00454-005-1206-y }}.
* {{인용 |first=Rolf |last=Schneider |title=Convex bodies: the Brunn-Minkowski theory |publisher=Cambridge University Press |location=Cambridge |year=1993 |isbn= }}.
* {{인용 |first=Terence |last=Tao |lastauthoramp=yes |first2=Van |last2=Vu |title=Additive Combinatorics |publisher=Cambridge University Press |year=2006 |isbn= }}.
* [https://ideas.repec.org/a/eee/ejores/v238y2014i3p774-785.html Mayer, A. and Zelenyuk, V. (2014) "Aggregation of Malmquist productivity indexes allowing for reallocation of resources," European Journal of Operational Research, 238:3, pp 774-785]
* [https://ideas.repec.org/a/eee/ejores/v240y2015i1p269-277.html Zelenyuk, V. (2015) "Aggregation of scale efficiency," European Journal of Operational Research, 240:1, pp 269-277.]

== 외부 링크 ==
* {{springer|title=Minkowski addition|id=p/m120210}}
* {{인용|title=On the tendency toward convexity of the vector sum of sets|authorlink=Roger Evans Howe|last=Howe|first=Roger|year=1979|publisher=[[Cowles Foundation|Cowles Foundation for Research in Economics]], Yale University|series=Cowles Foundation discussion papers|volume=538|url=http://econpapers.repec.org/RePEc:cwl:cwldpp:538}}
* [http://www.cgal.org/Pkg/MinkowskiSum2 Minkowski Sums], in [[Computational Geometry Algorithms Library]]
* [http://demonstrations.wolfram.com/TheMinkowskiSumOfTwoTriangles/ The Minkowski Sum of Two Triangles] and [http://demonstrations.wolfram.com/TheMinkowskiSumOfADiskAndAPolygon/ The Minkowski Sum of a Disk and a Polygon] by George Beck, [[The Wolfram Demonstrations Project]].
* [http://www.cut-the-knot.org/Curriculum/Geometry/PolyAddition.shtml Minkowski's addition of convex shapes] by Alexander Bogomolny: an applet
* [[Wikibooks:OpenSCAD User Manual/Transformations#minkowski]] by Marius Kintel: Application
{{함수 해석학}}

[[분류:볼록기하학 정리]]
[[분류:볼록기하학]]
[[분류:이항연산]]
[[분류:디지털 기하학]]
[[분류:기하 알고리즘]]
[[분류:변분해석학]]
[[분류:아벨 군론]]
[[분류:아핀기하학]]
[[분류:헤르만 민코프스키]]
[[분류:변분해석학]]