민코프스키 합

1. 개요[편집]

민코프스키 합 Minkowski Sum
정의	A ⊕ B = { a + b : a ∈ A, b ∈ B }
볼록 다각형끼리	모서리 벡터 병합으로 O(n + m)
비볼록 단순다각형	최악 Θ(n²m²) — 볼록 분해 후 합집합
지지함수	hA⊕B = hA + hB
주요 응용	구성공간 장애물 · GJK · 형태학 팽창 · CAM 오프셋

민코프스키 합은 두 집합의 모든 점 쌍을 더해서 얻는 집합

$$A \oplus B \;=\; \{\, a + b \;:\; a \in A,\ b \in B \,\}$$

이다. 동치인 읽기가 더 유용하다 — $A \oplus B = \bigcup_{b \in B} (A + b)$, 즉 $B$ 의 모든 점을 훑으며 $A$ 를 그만큼 평행이동시켜 쓸어낸 자국이다. 도형 $B$ 를 붓처럼 들고 $A$ 위를 칠했다고 생각하면 그림이 바로 그려진다.

이 단순한 연산이 서로 관계없어 보이는 분야들의 공통 조상 노릇을 한다. 로봇 경로계획의 장애물 부풀리기, GJK 알고리즘의 민코프스키 차, 수학적 형태학의 팽창(dilation), CAD/CAM의 공구 반경 보정, 볼록기하의 브룬-민코프스키 부등식이 전부 같은 $\oplus$ 다. 게다가 지지함수 쪽으로 넘어가면 이 연산은 그냥 덧셈이 된다 — 그 관점은 해당 문서에 정리되어 있으니 여기서는 계산과 기하 쪽을 본다.

2. 기본 성질[편집]

• 교환·결합법칙이 성립하고, 항등원은 $\{0\}$ 이다. 즉 $\oplus$ 아래에서 집합들은 가환 모노이드를 이룬다.
• 볼록성은 보존된다. $A, B$ 가 볼록이면 $A \oplus B$ 도 볼록. 더 나아가 임의의 집합에 대해 $\mathrm{conv}(A) \oplus \mathrm{conv}(B) = \mathrm{conv}(A \oplus B)$ 이므로, 볼록 껍질을 취하는 것과 더하는 것의 순서를 바꿔도 된다.
• 역원은 없다. $A \oplus (-A)$ 는 $\{0\}$ 이 아니라 $A$ 의 차집합체(difference body)라는 원점 대칭 도형이다. 이것이 뒤에 나오는 민코프스키 차 두 종류의 혼동의 뿌리다.
• $A \oplus B$ 의 지름은 각 지름의 합 이하가 아니라 합이고, 볼록체의 부피에는 브룬-민코프스키 부등식 $$\mathrm{vol}(A \oplus B)^{1/n} \;\ge\; \mathrm{vol}(A)^{1/n} + \mathrm{vol}(B)^{1/n}$$ 이 성립한다. 등호는 $A$ 와 $B$ 가 닮은꼴일 때. 등주부등식이 여기서 $B$ 를 공으로 놓아 떨어진다.¹
• $B$ 를 반지름 $r$ 인 공 $rB$ 로 잡으면 $A \oplus rB$ 는 $A$ 를 $r$ 만큼 부풀린 것이고, 볼록체에서는 슈타이너 공식에 의해 그 부피가 $r$ 의 다항식이 되며 계수로 표면적·평균폭이 나온다.

2.1. 차(difference)라는 말의 함정[편집]

같은 이름이 서로 다른 두 연산에 붙어 있다. 이건 표기 사고가 아니라 실제로 매년 사람을 잡는 지점이다.

• 민코프스키 차(충돌 판정 관용): $A \ominus B := A \oplus (-B) = \{a - b\}$. GJK 알고리즘이 “원점을 품는가”를 묻는 그 도형.
• 민코프스키 뺄셈(형태학 관용, erosion): $A \ominus B := \bigcap_{b\in B}(A - b) = \{z : B_z \subseteq A\}$. 이쪽은 $\oplus$ 의 수반(adjoint)이지 역원이 아니다.

앞엣것은 집합을 키우고 뒤엣것은 줄인다. 문서를 읽을 때는 저자가 로봇/게임 쪽인지 영상처리 쪽인지부터 확인하는 게 빠르다.²

3. 볼록 다각형 — O(n + m)[편집]

볼록 다각형 둘의 민코프스키 합은 놀랍도록 싸다. 핵심은 볼록 다각형이 곧 그 모서리 벡터들의 순환 정렬 목록이라는 사실이다. 반시계 방향으로 읽은 모서리 벡터들은 편각이 단조증가하고, 그 합은 0이다. 그리고

$A \oplus B$ 의 모서리 집합 = $A$ 의 모서리 집합 $\cup$ $B$ 의 모서리 집합 (편각 순으로 병합)

이 성립한다. 알고리즘은 그래서 다음 세 줄이다.

1. 두 다각형에서 $y$ 가 최소(동률이면 $x$ 최소)인 꼭짓점을 시작점으로 잡는다. 합의 시작점은 두 시작점의 합이다.
2. 두 모서리 벡터 목록을 편각 기준으로 병합 정렬한다(이미 각각 정렬되어 있으므로 병합만).
3. 시작점에서 병합된 순서대로 벡터를 이어 붙인다. 편각이 같은 두 모서리는 하나로 합친다.

정점이 각각 $n$, $m$ 개면 결과의 정점 수는 최대 $n+m$ 이고 시간도 $O(n+m)$ 이다. 3차원 볼록다면체에서는 결과의 복잡도가 $O(nm)$ 까지 커지지만(면 하나와 모서리들이 쌍으로 만난다), 여전히 다항식이고 법선 방향의 합병(normal fan의 공통 세분)으로 구성할 수 있다.

4. 비볼록 — 볼록 분해 후 합집합[편집]

한쪽이라도 오목하면 상황이 급격히 나빠진다. 평면 단순다각형 둘의 민코프스키 합은 최악의 경우 $\Theta(n^2m^2)$ 크기까지 커질 수 있다. 빗살처럼 생긴 두 다각형을 직교로 놓으면 격자 모양 구멍이 $n^2m^2$ 개 생기는 고전적 반례가 있다. 한쪽만 볼록이면 $\Theta(nm)$ 으로 내려간다.

실무의 표준 절차는 분해-합-합집합이다.

$$A \oplus B \;=\; \Bigl(\bigcup_i A_i\Bigr) \oplus \Bigl(\bigcup_j B_j\Bigr) \;=\; \bigcup_{i,j} \bigl(A_i \oplus B_j\bigr)$$

$A$ 를 볼록 조각 $A_i$ 로, $B$ 를 $B_j$ 로 볼록 분해한 뒤 볼록끼리의 쌍합을 전부 만들고 마지막에 합집합(불리언 유니온)을 취한다. 정확한 답이지만 조각 수의 곱만큼 유니온을 돌려야 해서, 실제 비용은 분해의 품질과 유니온 구현의 강건성에 좌우된다. 회전이 없는 경우엔 격자에 래스터화해서 근사로 때우는 것도 흔하다 — 정확도를 픽셀 크기로 사는 셈이다.

5. 구성공간과 경로계획[편집]

민코프스키 합이 가장 극적으로 쓰이는 곳. 평면에서 평행이동만 하는 로봇 $R$ (기준점을 원점에 두고 그린 모양)과 장애물 $O$ 를 생각하자. 로봇을 위치 $t$ 로 옮겼을 때 충돌한다는 것은

$$(R + t) \cap O \neq \emptyset \iff t \in O \oplus (-R)$$

이다. 즉 로봇 모양을 뒤집어 장애물에 더해 부풀리면, 로봇은 점 하나로 줄어든다. 이렇게 부풀린 장애물 $O \oplus (-R)$ 을 구성공간 장애물(C-obstacle)이라 부르고, 원래의 “뚱뚱한 로봇이 좁은 통로를 지나가는” 문제가 “점이 부풀린 장애물을 피해 가는” 문제로 정확히 환산된다. 경로 계획의 로드맵·가시성 그래프·격자 탐색이 전부 이 환산 위에서 돈다.

게임 쪽 실무에서도 같은 논리가 보인다. 내비게이션 메시를 만들 때 에이전트 반지름만큼 벽 안쪽으로 깎는 것은 원판 $rB$ 에 대한 민코프스키 뺄셈, 즉 형태학의 침식이고, 그 결과 런타임에 에이전트를 점으로 취급해도 몸이 벽을 뚫지 않는다.

한계도 분명하다. 회전이 들어가면 구성공간이 $SE(2)$ (3차원) 또는 $SE(3)$ (6차원)으로 올라가고, C-obstacle을 명시적으로 만드는 비용이 감당 불가가 된다. 그래서 회전을 포함하는 현대적 경로계획은 C-obstacle을 만들지 않고 무작위 샘플링 + 충돌 질의로 우회한다(RRT 계열).³ 즉 민코프스키 합은 “환산은 항상 옳지만 명시적 구성은 저차원에서만 쓴다”는 도구다.

6. 충돌 판정과 형태학[편집]

충돌 판정. $A \cap B \neq \emptyset \iff 0 \in A \oplus (-B)$ 라는 한 줄이 충돌 감지 좁은 단계 전체의 근거다. 그리고 실제 알고리즘은 $A \oplus (-B)$ 를 만들지 않는다 — 방향을 주면 그 방향 최원점을 돌려주는 오라클만 합성해서 쓴다. 그 오라클 대수가 지지함수 문서에 있다.⁴ 겹쳤을 때의 침투 깊이는 원점에서 $A \oplus (-B)$ 의 경계까지의 최단거리이며, EPA가 그것을 계산한다.

형태학. 이진 영상에서 구조요소 $B$ 에 의한 팽창은 정의상 $\delta_B(X) = X \oplus B$ 이고(문헌에 따라 구조요소의 원점 대칭 $\check B$ 를 쓰는 관례도 있다), 침식은 앞서 본 민코프스키 뺄셈이다. 즉 수학적 형태학의 두 기본 연산이 민코프스키 합/뺄셈 그 자체다. 회색조로 확장하면 지시함수 대신 함수가 들어가면서 하한 합성곱이 되고, 그래서 형태학·볼록해석·열대대수가 같은 $(\min,+)$ 구조를 공유하게 된다.

CAD/CAM. 공구 반경 보정(cutter radius compensation)은 가공 형상을 공구 원판으로 민코프스키 합/뺄셈한 것이고, 3D 프린팅의 서포트 여유, PCB 설계 규칙의 클리어런스 검사도 같은 연산이다. 오프셋 곡선이 자기교차하며 생기는 그 악명 높은 루프들은 민코프스키 합의 경계가 입력 경계의 부분집합이 아니라는 사실의 실물이다.

7. 관련 문서[편집]

• 지지함수 · 하한 합성곱 · 볼록 껍질
• GJK 알고리즘 · 충돌 감지 · 물리 엔진 · 경계 볼륨 계층
• 수학적 형태학 · 거리 변환
• 내비게이션 메시 · 경로 계획 · RRT · 볼록 분해
• 볼록 최적화 · 들로네 삼각분할

8. Footnotes[편집]

1. 브룬-민코프스키 부등식은 이름값에 비해 응용이 무섭게 넓다. 등주부등식, 프레코파-라인들러 부등식, 정보이론의 엔트로피 멱 부등식이 전부 이 한 줄의 친척이다. “두 도형을 더하면 부피가 예상보다 커진다”는 문장이 어쩌다 정보이론까지 갔는지는 볼록기하 강의의 단골 하이라이트. ↩

2. 더 얄궂은 건 두 정의가 볼록체에서도 다르다는 점이다. 원판 $A$ 와 작은 원판 $B$ 에 대해 형태학적 뺄셈은 $A$ 를 깎아 더 작은 원판을 주고, 충돌 판정 쪽 “차”는 $A$ 를 부풀려 더 큰 원판을 준다. 방향이 아예 반대라 부호 실수 한 번이면 로봇이 벽에 박히거나 통로를 영원히 못 지나간다. ↩

3. 회전을 포함한 $SE(3)$ 구성공간의 장애물을 명시적으로 계산하는 시도는 1980년대에 실제로 있었고, 결론은 “6차원 다면체 복합체를 만들 바에는 충돌 질의를 백만 번 하는 게 싸다”였다. 샘플링 기반 계획법이 이겨서가 아니라 명시적 표현이 스스로 무너져서 지금의 구도가 됐다는 쪽이 정확하다. ↩

4. 반대로 지지함수 쪽에서 보면 $h_{A\oplus B} = h_A + h_B$ 라 이 모든 복잡함이 사라진다. 그런데 그 대가로 비볼록 정보가 조용히 버려진다 — 오목한 메시를 넣으면 볼록 껍질의 답이 나온다. 세상에 공짜는 없고, 여기서 지불하는 화폐는 오목함이다. ↩