https://www.youtube.com/watch?v=OL6zwhV4rc4
유클리드 공간에서 시간이 정지된 (시간축을 다루지 않는) 3차원 벡터에 관한 자료를 조사하다가
우연히 시간을 다루는 민코프스키 시공간을 접하고, 민코프스키 합이라는 수학 공식을 접하게 되었습니다.
수학에 깊이 관여하진 않았기 때문에 부정확할 수도 있지만,
민코프스키 합은 컴퓨터 공학 특히 선형대수 , 길찾기에서 충분히 적용 가능한 공식이기 때문에 기록해보겠습니다.
민코프스키 합은 2차원 유클리드 공간에 볼록한 다각형 (어떤 선분도 다각형 외부로 나가지 않는 단순 다각형 , 일반적인 다각형이라고 생각하시면 됩니다.)P와 R가 존재한다고 가정합니다. 민코프스키 합은 P와 R의 위치 벡터 집합의 모든 원소를 더하여 새로운 집합을 만듭니다. 즉 민코프스키 합 Q = P + R = {p + r | p ∈ P and r ∈ R} 입니다.
즉 민코프스키 합으로 생성된 집합 Q는 P에 속하는 모든 영역의 좌표 (x1, y1)와 R에 속하는 모든 영역의 좌표 (x2, y2)에 대해, 있을 수 있는 모든 (x1 + x2, y1 + y2) 조합이 나타내는 영역의 도형입니다.
도형 Q 는 P 의 꼭지점 개수와 R 의 꼭지점 개수를 합친 것보다 더 많은 꼭지점을 가지고, P와 R이 볼록한 다각형일 때 Q도 볼록한 다각형입니다.
민코프스키 합으로 도출된 도형 Q가 중요한 이유는 도형 Q의 극점이 P와 R의 극점과 평행을 이루는 선분이 반드시 존재하기 때문입니다. 민코프스키를 통해 얻은 집합 Q는 P와 R이 가지는 모든 벡터의 합집합입니다. 이를 좀 더 쉽게 말해 도형 Q의 모든 변은 P 또는 R의 한 변과 평행합니다. 그 이유는 P와 R의 각 극점이 독립적으로 더해지기 때문에, 결과로 나오는 도형의 극점들은 평행한 변을 가지기 때문입니다. 이것은 각 집합의 변들이 평행하게 이동되었기 때문입니다.
도형 Q가 P와 R의 선분과 모두 평행하고, P와 R의 꼭지점을 확장 시키기 때문에 도형 Q는 P와 R보다 항상 넓습니다. 즉 도형 P와도형 R이 도형 Q에 포함되어 있을 때 넓은 도형인 P를 기준으로 R이 P의 외각을 따라 이동할 때 Q의 범위에서 벗어나지 않는 곳이 반드시 존재합니다. 즉 민코프스키 합을 활용하여 움직이는 물체 R이 장애물 P에 부딪히지 않는 형태로 이동하는 최소한의 길 Q를 찾는 알고리즘을 설계할 수 있습니다. 이는 로봇 공학에서 연구되고 있는 알고리즘 형태입니다.
https://ieeexplore.ieee.org/abstract/document/1348370
Accurate Minkowski sum approximation of polyhedral models
We present an algorithm to approximate the 3D Minkowski sum of polyhedral objects. Our algorithm decomposes the polyhedral objects into convex pieces, generates pairwise convex Minkowski sums and computes their union. We approximate the union by generating
ieeexplore.ieee.org
민코프스키 합은 집합들 간의 선형 변환(linear transformation)을 가능하게 합니다. 따라서 원래의 집합이 평행 이동되고 회전되더라도, 민코프스키 합의 결과로 얻은 도형의 꼭지점들은 여전히 평행한 성질을 유지합니다.
민코프스키의 합의 선형 변환 특성을 사용해 2차원 공간에서 두 도형의 거리를 계산하는 알고리즘의 시간 복잡도를 효과적으로 줄일 수 있습니다. 2차원 유클리드 공간에 도형 P와 Q가 있다고 가정하겠습니다. 두 도형 사이의 거리는 항상 두 꼭지점 간이나 꼭지점과 모서리 간에 발생하므로 거리를 시간에 찾을 수 있습니다. 그러나 민코프스키 합을 높은 수준으로 응용하면 복잡도를 O(|P| + |Q|)로 줄일 수 있습니다.
만약 를 영점 S(0,0)을 중심으로 반사하여 다각형 를 얻으면, 문제는 점 S(0,0)에서 민코프스키 합 내의 어떤 점과의 최소 거리를 찾는 것으로 축소됩니다. 우리는 다음 아이디어를 사용하여 이 거리를 선형 시간에 찾을 수 있습니다. 만약 S(0,0)가 민코프스키 합으로 형성된 다각형의 내부에 있거나 경계 상에 있다면 거리는 0이고, 그렇지 않으면 거리는 민코프스키 합 다각형의 어떤 꼭지점과 점 S(0,0) 사이의 거리를 측정해서 얻을 수 있습니다. 민코프스키 합이 선형 시간에 계산될 수 있기 때문에, 두 볼록 다각형 사이의 거리를 찾는 알고리즘은 선형 시간(O(|P| + |Q|))에 동작합니다.
https://cp-algorithms.com/geometry/minkowski.html
Minkowski sum of convex polygons - Algorithms for Competitive Programming
Minkowski sum of convex polygons Definition Consider two sets $A$ and $B$ of points on a plane. Minkowski sum $A + B$ is defined as $\{a + b| a \in A, b \in B\}$. Here we will consider the case when $A$ and $B$ consist of convex polygons $P$ and $Q$ with t
cp-algorithms.com