민코프스키 덧셈
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
민코프스키 덧셈은 두 집합의 원소들을 더하여 새로운 집합을 생성하는 연산이다. 두 집합 A와 B의 민코프스키 합은 A의 각 원소와 B의 각 원소를 더하여 얻어진 모든 가능한 합의 집합으로 정의된다. 이 연산은 기하학, 특히 볼록 집합의 연구에서 중요한 역할을 하며, 수학적 형태학, 모션 계획, 충돌 감지 등 다양한 분야에 응용된다. 민코프스키 덧셈은 영집합을 항등원으로 가지며, 공집합과의 합은 공집합이다. 볼록 집합의 경우 민코프스키 덧셈은 볼록 폐포 연산과 가환적이며, 볼록 폐포의 덧셈은 각 집합의 볼록 폐포 덧셈과 같다. 알고리즘을 통해 평면상의 볼록 다각형의 민코프스키 합을 효율적으로 계산할 수 있다.
더 읽어볼만한 페이지
- 변분해석학 - 하방미분
하방미분은 볼록 함수에서 미분 불가능한 지점에서도 미분과 유사한 정보를 제공하는 개념으로, 특정 조건을 만족하는 실수 집합으로 정의되며, 미분 가능성, 전역 최솟점, 볼록 함수 합에 대한 성질을 가지고 다변수 함수로 일반화될 수 있으며, 1960년대 초에 소개되었다. - 변분해석학 - 반연속 함수
반연속 함수는 위상 공간에서 전순서 집합으로 가는 함수로서, 상반연속 함수는 특정 지점에서의 상극한이 함수값보다 작거나 같고, 하반연속 함수는 하극한이 함수값보다 크거나 같도록 정의되며, 함수의 극한, 최적화 문제, 연속 함수 등과 관련되어 다양한 분야에 응용된다. - 기하 알고리즘 - 최근접 이웃 탐색
최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다. - 기하 알고리즘 - 신발끈 공식
신발끈 공식은 평면 다각형의 꼭짓점 좌표를 이용해 면적을 구하는 공식으로, 사다리꼴, 삼각형, 행렬식 등으로 표현되며, 꼭짓점들을 특정 순서로 나열하여 계산하는 모습이 신발끈을 묶는 모양과 유사하여 붙여진 이름이다. - 볼록기하학 정리 - 브라우어르 고정점 정리
브라우어르 고정점 정리는 콤팩트 볼록 집합에서 자기 자신으로 가는 연속 함수는 반드시 고정점을 가진다는 정리로, 다양한 공간에서 여러 형태로 표현되며 함수해석학에서 중요한 역할을 한다. - 볼록기하학 정리 - 헬리의 정리
헬리의 정리는 d차원 공간의 볼록 부분집합들 중 임의의 d+1개의 교집합이 공집합이 아니면 전체 집합의 교집합도 공집합이 아니라는 정리이다.
민코프스키 덧셈 | |
---|---|
개요 | |
정의 | 두 개의 벡터 집합 A와 B의 민코프스키 합은 A의 각 벡터와 B의 각 벡터를 더하여 얻은 벡터들의 집합임 |
표기법 | A + B |
응용 분야 | 이미지 처리 로봇 공학 볼록 기하학 수리 형태학 |
성질 | |
교환 법칙 | A + B = B + A |
결합 법칙 | (A + B) + C = A + (B + C) |
항등원 | {0} (영벡터 집합) |
분배 법칙 | 람다(A + B) = 람다A + 람다B (람다는 스칼라) |
볼록 집합 | A와 B가 볼록 집합이면 A + B도 볼록 집합임 |
콤팩트 집합 | A와 B가 콤팩트 집합이면 A + B도 콤팩트 집합임 |
추가 정보 | |
참고 문헌 | Hadwiger, Hugo (1950). Mathematische Zeitschrift 53 (3): 210–218. doi:10.1007/BF01175656. Li, Wei (Fall 2011). GPU-Based Computation of Voxelized Minkowski Sums with Applications (PhD). UC Berkeley. pp. 13–14. Lozano-Pérez, Tomás (February 1983). IEEE Transactions on Computers C-32 (2): 108–120. doi:10.1109/TC.1983.1676196. |
2. 정의 및 예시
두 집합 ''A''와 ''B''의 민코프스키 덧셈 ''A'' + ''B''는 ''A''에 속하는 원소 ''a''와 ''B''에 속하는 원소 ''b''의 모든 가능한 합 ''a'' + ''b''로 이루어진 집합이다. 수식으로는 다음과 같이 정의된다.
:
예를 들어, 2차원 평면 에서 두 개의 삼각형을 나타내는 꼭짓점 집합 ''A''와 ''B''가 다음과 같다고 하자.
:
:
이 두 집합의 민코프스키 덧셈은 다음과 같다.
:
이 결과 집합의 점들을 구하면 이며, 이는 육각형의 꼭짓점을 이룬다.
다른 예시로, 실수 또는 복소수 체 에서 열린 공 또는 닫힌 공의 민코프스키 합을 생각해보자. 에서 원점을 중심으로 하고 반지름이 인 닫힌 공을 이라고 정의하면, 모든 에 대해 다음이 성립한다.
:
또한, 모든 스칼라 에 대해 (단, 또는 일 때) 다음이 성립한다.
:
4. 응용
민코프스키 덧셈은 수학적 형태학에서 중요한 역할을 한다. 이는 2차원 컴퓨터 그래픽스의 브러시-스트로크 패러다임에서 나타나는데, 다양한 용도로 활용되며 특히 도널드 E. 크누스가 메타폰트에서 사용한 것으로 유명하다. 또한 3차원 컴퓨터 그래픽스에서는 솔리드 스윕 연산의 기반이 된다. 이 외에도 지구 이동 거리와 밀접한 관련이 있으며, 이를 통해 최적 수송 문제와도 연결된다.
4. 1. 모션 계획 (Motion Planning)
민코프스키 덧셈은 물체가 장애물을 피해 움직이는 경로를 찾는 모션 계획 문제에 활용된다. 모션 계획에서는 물체가 존재할 수 있는 모든 위치와 자세의 집합인 짜임새 공간(Configuration Space, 또는 구성 공간)을 계산하는 것이 중요한데, 이때 민코프스키 덧셈이 사용된다.가장 간단한 예로, 평면 위에서 물체가 평행이동만 하는 경우를 생각해 볼 수 있다. 이 경우, 물체의 위치는 물체 위의 한 고정된 점의 좌표로 나타낼 수 있다. 이때 짜임새 공간, 즉 물체가 장애물과 충돌하지 않고 위치할 수 있는 모든 지점의 집합은 다음과 같이 계산된다. 먼저 장애물들의 집합을 생각한다. 그리고 움직이려는 물체를 원점을 기준으로 180도 회전시킨 집합을 만든다. 이 두 집합의 민코프스키 덧셈 결과가 바로 짜임새 공간이 된다.
4. 2. 수치 제어 (NC) 가공
수치 제어(NC) 가공에서 NC 공구를 프로그래밍할 때는 민코프스키 덧셈의 원리가 이용된다. 즉, 절삭 공구의 이동 경로(궤적)와 절삭 공구 자체의 모양을 민코프스키 덧셈하면, 그 결과가 재료에서 실제로 깎여 나가는 부분의 형태와 일치한다는 점을 활용하는 것이다. 이를 통해 원하는 형상으로 정밀하게 재료를 깎아낼 수 있다.4. 3. 3D 솔리드 모델링
OpenSCAD와 같은 3D 솔리드 모델링 소프트웨어에서 민코프스키 덧셈은 한 도형을 다른 도형의 윤곽을 따라 이동시키며 결합하여 새로운 복합 도형을 생성하는 데 사용된다.4. 4. 충돌 감지 (Collision Detection)
민코프스키 합, 특히 민코프스키 차는 GJK 알고리즘과 함께 물리 엔진에서 볼록 껍질의 충돌 감지를 계산하는 데 자주 사용된다.4. 5. 집성 이론(Aggregation Theory)
민코프스키 덧셈은 집성 이론 (Aggregation Theory)에서 집계 대상이 되는 각각의 물체가 집합으로 특정될 경우에 종종 사용된다.[17][18][9][10]5. 알고리즘
민코프스키 덧셈을 계산하는 알고리즘은 덧셈 대상이 되는 집합의 형태에 따라 다양하다. 특히, 평면 상의 두 볼록 다각형의 민코프스키 덧셈은 각 다각형의 꼭짓점 수에 비례하는 효율적인 시간 안에 계산할 수 있는 알고리즘이 알려져 있다. 집합이 볼록하지 않은 경우에는 계산 복잡도가 증가한다. 구체적인 알고리즘과 시간 복잡도 분석은 아래 하위 섹션에서 자세히 다룬다.
5. 1. 평면 상의 두 볼록 다각형
평면 상의 두 볼록 다각형 P와 Q가 각각 m개와 n개의 꼭짓점을 가진다고 할 때, 이들의 민코프스키 합은 최대 m + n개의 꼭짓점을 갖는 볼록 다각형이다. 이 민코프스키 합은 다음과 같은 간단한 절차를 통해 O(m + n) 시간에 계산할 수 있다.먼저, 각 다각형의 변들을 경계를 따라 반시계 방향으로 나열한다고 가정한다. 이렇게 하면 각 볼록 다각형의 변들은 극각 순서대로 정렬된다.
다음으로, P와 Q에서 얻은 방향성 변들의 정렬된 순서를 단일 정렬 순서 S로 병합한다. 이때 각 변을 원래 방향과 평행하게 유지하면서 자유롭게 움직일 수 있는 단단한 화살표로 생각할 수 있다.
마지막으로, 순서 S의 순서대로 다음 화살표의 꼬리를 이전 화살표의 머리에 붙여서 모든 화살표를 조립한다. 이렇게 만들어진 폴리곤 체인이 바로 P와 Q의 민코프스키 합인 볼록 다각형이 된다.
5. 2. 기타 경우
한 다각형이 볼록이고 다른 하나는 그렇지 않다면, 그들의 민코프스키 덧셈의 복잡도는 O(''nm'')이다. 두 다각형 모두 비볼록이라면, 그들의 민코프스키 덧셈 복잡도는 O((''mn'')2)이다.6. 본질적 민코프스키 덧셈
유클리드 공간의 두 부분집합에 대한 '''본질적 민코프스키 덧셈'''(essential Minkowski sum)은 +e 기호로 표기한다. 일반적인 민코프스키 덧셈은 다음과 같이 정의된다.
:
이를 바탕으로, '''본질적 민코프스키 덧셈'''은 다음과 같이 정의된다.
:
여기서 ''μ''는 ''n''-차원 르베그 측도를 나타낸다. 즉, 일반적인 민코프스키 덧셈과 달리 두 집합의 교집합(∩)이 공집합(∅)이 아닌지만 보는 것이 아니라, 그 교집합의 르베그 측도가 0보다 큰지를 확인한다.
"본질적"이라는 용어는 지시 함수와 관련된 다음 속성 때문에 사용된다. 일반적인 민코프스키 덧셈의 지시 함수는 다음과 같이 상한(sup)으로 표현된다.
:
반면, 본질적 민코프스키 덧셈의 지시 함수는 본질적 상한(ess sup)으로 표현된다.
:
여기서 "ess sup"은 본질적 상한을 의미한다.
7. Lp 민코프스키 덧셈
:
:
민코프스키 부등식에 의해서, 함수
참조
[1]
간행물
Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt
https://gdz.sub.uni-[...]
2023-01-12
[2]
학위논문
GPU-Based Computation of Voxelized Minkowski Sums with Applications
https://escholarship[...]
UC Berkeley
2011-09-22 #Fall 2011을 2011년 가을로 해석
[3]
간행물
Spatial Planning: A Configuration Space Approach
https://lis.csail.mi[...]
1983-02-01
[4]
간행물
On regularly convex sets in the space conjugate to a Banach space
[5]
서적
Convex bodies: The Brunn–Minkowski theory
https://archive.org/[...]
Cambridge University Press
[6]
서적
Convex bodies: The Brunn–Minkowski theory
Cambridge University Press
[7]
웹사이트
The Theorem of Barbier (Java)
http://www.cut-the-k[...]
[8]
간행물
Properties of the d-dimensional earth mover's problem
[9]
간행물
Aggregation of scale efficiency
https://ideas.repec.[...]
[10]
간행물
Aggregation of Malmquist productivity indexes allowing for reallocation of resources
https://ideas.repec.[...]
[11]
간행물
"''p''-means of convex bodies"
[12]
인용
Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt
[13]
뉴스
On regularly convex sets in the space conjugate to a Banach space
[14]
서적
Convex bodies: The Brunn–Minkowski theory
Cambridge University Press
[15]
서적
Convex bodies: The Brunn–Minkowski theory
Cambridge University Press
[16]
웹사이트
The Theorem of Barbier (Java)
http://www.cut-the-k[...]
[17]
간행물
Aggregation of scale efficiency
https://ideas.repec.[...]
[18]
간행물
Aggregation of Malmquist productivity indexes allowing for reallocation of resources
https://ideas.repec.[...]
[19]
인용
"''p''-means of convex bodies"
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com