민코프스키 덧셈

빨간 도형은 파란 도형과 초록색 도형의 민코프스키 덧셈이다.

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

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

유사하게, 민코프스키 차(또는 기하학적 차)는 다음과 같이 정의된다:

$A-B=\{\mathbf {c} \,|\,\mathbf {c} +B\subseteq A\}.$

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

$A-B=(A^{c}+(-B))^{c}.$

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

민코프스키 합 A + B

B

A

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

예시

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

$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),(0,-1),(1,-2)\},$

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

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

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

공집합은 공집합은 다른 모든 부분집합을 없애기 때문에 민코프스키 덧셈에서 중요하다: 벡터 공간의 모든 부분집합 S에 대해서, 공집합과의 합은 공집합이다:

$S+\emptyset =\emptyset .$

빨간 집합의 볼록 폐포에서, 각각의 파란 점은 어떤 빨간 점의 볼록 조합이다.

집합의 민코프스키 덧셈. 정사각형 Q₁=[0,1]²과 Q₂=[1,2]²의 덧셈은 정사각형 Q₁+Q₂=[1,3]²이다.

민코프스키 덧셈의 볼록 폐포

민코프스키 덧셈은 볼록 폐포를 취하는 연산에 대해서 다음의 명제에서 보인 것 같이 잘 동작한다:

• 실 벡터 공간의 어떤 진부분집합 S₁와 S₂에 대해서, 그 민코프스키 덧셈의 볼록 폐포는 그 볼록 폐포의 민코프스키 덧셈이다:

$\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}).$

수학 용어학에서, 민코프스키 덧셈과 볼록 폐포를 만드는 연산은 가환 연산이다.

S가 볼록 집합이라면 $\mu S+\lambda S$는 볼록 집합이다; 게다가 모든 $\mu ,\lambda \geq 0$에 대해서 다음이 성립한다:

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

반대로, 음이 아닌 어떤 실수 $\mu ,\lambda$에 대해서 이 "분배법칙"이 적용되면 집합은 볼록이다.

그림은 A + A ⊋ 2A인 비볼록 집합의 예시를 보여준다.

A + A ≠ 2A인 비볼록 집합의 예시

1차원의 예시: B=[1,2]∪[4,5]. 이것은 쉽게 2B=[2,4]∪[8,10]이지만 B+B=[2,4]∪[5,7]∪[8,10]인 것을 계산할 수 있다. 따라서, 역시 B+B ⊋ 2B이다.

민코프스키 덧셈은 이차원 볼록체의 둘레에서 선형적으로 작용한다: 덧셈의 둘레는 둘레의 합과 같다. 게다가, K가 정폭도형(의 내부)이면, K와 그것을 180°돌린 도형의 민코프스키 덧셈은 원판이다. 이 두 사실을 결합하면 정폭도형의 둘레에서 바르비에의 정리의 간략하게 증명할 수 있다.

적용

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

모션 계획

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

수치 제어 (NC) 가공

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

3d 솔리드 모델링

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

집계 이론

민코프스키 덧셈은 집계 이론에서 집계된 각각의 물체가 집합으로 특정될 경우에 종종 사용된다.

민코프스키 덧셈을 계산하는 알고리즘

민코프스키 덧셈과 볼록 폐포. 빨간 점의 쌍으로 이루어진 (왼쪽에 있는) 비볼록 집합 네 개의 덧셈으로 생긴 (오른쪽에 있는) 16개의 진한 빨간색 점. (분홍색으로 칠해진) 볼록 폐포는 더하기 기호 (+)를 포함한다: 오른쪽 더하기 기호는 왼쪽 더하기 기호의 덧셈이다.

평면의 경우

평면의 볼록 다각형 두 개

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

기타

한 다각형이 볼록이고 다른 것은 아니라면, 그 민코프스키 덧셈의 완비성은 O(nm)이다. 둘 다 비볼록이라면, 그 민코프스키 덧셈의 완비성은 O((mn)²)이다.

본질적 민코프스키 덧셈

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

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

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

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

여기서 μ는 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 민코프스키 덧셈

$\mathbb {R} ^{n}$의 콤팩트 볼록 집합 K와 L에 대해서, 민코프스키 합은 볼록 집합의 지지 함수로 설명될 수 있다:

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

p ≥ 1일 때, Firey는 L^p 민코프스키 합을 원점을 다음과 같이 포함하는 $\mathbb {R} ^{n}$에 있는 콤팩트 볼록 집합 K와 L의 K+_pL로 정의했다:

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

민코프스키 부등식에 의해서, 함수 h_K+pL은 다시 양의 동차이고 볼록이고 따라서 콤팩트 볼록 함수의 지지 함수이다. 이 정의는 L^p Brunn-Minkowski theory에서 근본적이다.

같이 보기

• 팽창
• 침식
• 구간 산술
• 혼합 부피 (a.k.a. Quermassintegral 또는 intrinsic volume)
• 평행 곡선
• 섀플리-포크먼 보조정리
• Zonotope
• 합성곱

참조

• Arrow, Kenneth J.; Hahn, Frank H. (1980). 《General competitive analysis》. Advanced textbooks in economics 12 reprint of (1971) San Francisco, CA: Holden-Day, Inc. Maematical economics texts. 6판. Amsterdam: North-Holland. ISBN 0-444-85497-5. MR 439057. 
• Gardner, Richard J. (2002), “The Brunn-Minkowski inequality”, 《Bull. Amer. Math. Soc. (N.S.)》 39 (3): 355–405 (electronic), doi:10.1090/S0273-0979-02-00941-2 
• Green, Jerry; Heller, Walter P. (1981). 〈1 Mathematical analysis and convexity with applications to economics〉. Arrow, Kenneth Joseph; Intriligator, Michael D. 《Handbook of mathematical economics, Volume I》. Handbooks in economics 1. Amsterdam: North-Holland Publishing Co. 15–52쪽. doi:10.1016/S1573-4382(81)01005-9. ISBN 0-444-86126-2. MR 634800. 2012년 12월 17일에 원본 문서에서 보존된 문서. 2017년 11월 22일에 확인함. 
• Henry Mann (1976), 《Addition Theorems: The Addition Theorems of Group Theory and Number Theory》 Correct reprint of 1965 Wiley판, Huntington, New York: Robert E. Krieger Publishing Company, ISBN 0-88275-418-1 – http://www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html 경유 
• Rockafellar, R. Tyrrell (1997). 《Convex analysis》. Princeton landmarks in mathematics Reprint ofe 1979 Princeton maematical series 28판. Princeton, NJ: Princeton University Press. xviii+451쪽. ISBN 0-691-01586-4. MR 1451876. MR274683. 
• Nathanson, Melvyn B. (1996), 《Additive Number Theory: Inverse Problems and Geometry of Sumsets》, GTM 165, Springer, Zbl 0859.11003 .
• Oks, Eduard; Sharir, Micha (2006), “Minkowski Sums of Monotone and General Simple Polygons”, 《Discrete and Computational Geometry》 35 (2): 223–240, doi:10.1007/s00454-005-1206-y .
• Schneider, Rolf (1993), 《Convex bodies: the Brunn-Minkowski theory》, Cambridge: Cambridge University Press .
• Tao, Terence & Vu, Van (2006), 《Additive Combinatorics》, Cambridge University Press .
• 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
• Zelenyuk, V. (2015) "Aggregation of scale efficiency," European Journal of Operational Research, 240:1, pp 269-277.

외부 링크

• “Minkowski addition”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Howe, Roger (1979), 《On the tendency toward convexity of the vector sum of sets》, Cowles Foundation discussion papers 538, Cowles Foundation for Research in Economics, Yale University 
• Minkowski Sums, in Computational Geometry Algorithms Library
• The Minkowski Sum of Two Triangles and The Minkowski Sum of a Disk and a Polygon by George Beck, The Wolfram Demonstrations Project.
• Minkowski's addition of convex shapes by Alexander Bogomolny: an applet
• Wikibooks:OpenSCAD User Manual/Transformations#minkowski by Marius Kintel: Application