구사과

1. Separating Hyperplane Theorem 2차원 평면에 겹치지 않는 두 원이 있을 때, 두 원을 분리하는 직선을 찾을 수 있을까? 다시 말해, 직선의 한 쪽에 첫 번째 원이, 직선의 다른 쪽에 두 번째 원이 존재하게 직선을 그을 수 있을까? 어렵지 않게, 두 원의 공통 접선을 적절히 그어서 나누면 될 것이다. 같은 원리로, 겹치지 않는 두 볼록 다각형이 있을 때 둘을 분리하는 직선 역시 찾을 수 있다. 조금 더 복잡하지만, 3차원 공간에서도 겹치지 않는 두 볼록 다면체를 분리하는 평면이 존재할 것 같다. 즉, 평면의 한 쪽에 볼록 다면체 하나가, 다른 한 쪽에 볼록 다면체 하나가 있는 것이다. 이를 $n$ 차원으로 일반화하면 다음과 같다. 두 개의 Disjoint한 ($A \cap B ..

알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할 정복 기법을 그래프에서도 적용할 수 있는 좋은 프레임워크가 생겼고, 그 결과 중 하나가 Expander Decomposition이다. Expander는 잘 연결된 그래프를 뜻한다. 보통 그래프..

티스토리 렌더링 문제로 수식이 많이 깨진다. 일단 깨진 형태로 올려두지만 쉽게 볼 수 있는 PDF를 첨부한다. PDF를 보는 것을 추천한다. Chapter 4. $\boxdot$ 연산자의 빠른 구현 현재 우리의 알고리즘이 $O(N^5)$ 인 이유는 다음과 같다: $\boxdot$ 연산자가 $O(N^3)$ 에 구현됨 $\boxdot$ 연산자를 $O(N^2)$ 번 호출함 잠시 $\boxdot$ 연산자의 실제 이름을 짚고 넘어가자면, 논문에서는 위 연산자가 unit-Monge matrix-matrix distance multiplication 라는 이름으로 소개되었다. Part 1에서는 괜히 글이 어렵다는 인상을 줄 것 같아서 의도적으로 언급하지 않은 이름이다. 이제부터는 (순열의) unit-Monge 곱 이..