위키득계정 ↗
과학

민코프스키 합

민코프스키 합과학
영어
Minkowski sum
정의
A+B={a+b | a∈A, b∈B}
좌표 연산
각 좌표 성분을 더함
볼록 다각형
변의 방향 순서를 병합하여 계산 가능
민코프스키 합은 두 점 집합에서 점을 하나씩 선택해 더하여 만들 수 있는 모든 점의 집합이다. A+B={a+b | a∈A, b∈B}로 나타내며, 평면 도형의 합은 면적을 더하거나 두 도형을 겹쳐 놓는 연산과 다르다.

점들의 덧셈

평면에서 a=(a₁,a₂), b=(b₁,b₂)라면 합은 (a₁+b₁,a₂+b₂)다. 가능한 모든 선택을 모으므로 결과는 보통 하나의 점이 아니라 도형이다. 한 집합이 점 하나뿐이면 다른 집합을 그 점의 위치 벡터만큼 평행이동한 결과가 된다.

직사각형의 예

A=[0,2]×[0,1], B=[0,1]×[0,3]이면 A+B=[0,3]×[0,4]다. 가로와 세로 좌표에서 가능한 합의 범위를 각각 계산하면 된다. 원래 두 직사각형의 넓이는 2와 3이지만 결과의 넓이는 12이므로 넓이를 단순히 더하는 연산이 아님을 확인할 수 있다.

볼록 다각형의 계산

내부를 포함한 두 볼록 다각형의 민코프스키 합도 볼록 다각형이다. 꼭짓점이 각각 n개와 m개라면 결과의 꼭짓점 수는 최대 n+m개다. 양쪽 경계가 반시계 방향으로 정리되어 있을 때 변 벡터의 방향 순서를 병합하고 같은 방향의 변을 합치는 방식으로 O(n+m)에 구할 수 있다.

서로 다른 연산 구분

집합의 합집합은 두 집합 중 어느 한쪽에 속하는 점을 모은다. 민코프스키 합은 점끼리 더한 위치를 모으므로 합집합과 구별해야 한다. 또한 볼록 다각형을 위한 선형 시간 계산법을 꼭짓점이 임의 순서로 주어진 점 목록이나 오목한 다각형에 그대로 적용할 수는 없다.

관련 문서

볼록집합 / 볼록 껍질 / 벡터 / 합집합 / 평행이동 / 시간 복잡도