주어진 원들을 분리하는 영역들

한 볼록다각형 내부에 개의 원들이 있어, 어떤 두 원을 잡아도 서로 겹치지 않고 하나가 다른 하나의 내부에 있지 않았다고 한다. 이 때, 내부의 영역을 개의 볼록다각형 영역으로 분할하여, 각각의 영역이 정확히 한 개의 주어진 원이 들어가게 할 수 있다.

예전에 후배가 풀어보라고 던져줬는데 얼떨결에 그 자리에서 보자마자 키 아이디어를 맞춰버려서 내 기억엔 훈훈한 문제로 남아있다… 문제에서는 볼록다각형 내부에서 잡는 것으로 되어 있지만 사실 별 필요 없는 조건이고 그냥 평면 전체에서 생각해도 된다. 단 등장하는 영역은 볼록다각형이 아니라 경계가 유한개의 선분이나 반직선으로 이루어진 볼록도형이라고 고쳐야 함. 원래 문제로 돌아가려면 그냥 와의 교집합 씌워주면 된다.

분할이 완성된 그림을 떠올려보면 직관적으로 어떤 개념 하나가 떠오르게 되는데, 바로 근축(radical axis)이다. 근축이란 두 원에 대한 방멱(power; 중심이 이고 반지름이 인 원에 대한 같은 평면 위의 점 의 방멱은 로 정의된다)이 같은 점들의 자취로, 보통 직선이 됨이 알려져 있다. 또한 두 원이 겹치지 않고 하나가 다른 하나 내부에 들어가있지 않은 상황이라면 이 직선은 평면을 두 개의 반평면으로 나누고 각각에 원 하나씩이 들어간다. 개의 근축들을 그리면서 생각해보면, 문제의 조건을 만족시키는 개의 볼록다각형들의 선분을 근축들의 부분집합으로 잡는 것으로 해결할 수 있다.

이를 조금 더 간결하게 표현하기 위해, 각각의 원을 이라 하고, 원 에 대한 점 의 방멱을 편의상 라고 쓸 때, 영역 를 로 정의한다. 즉 에 대한 방멱이 다른 원들에 대한 방멱보다 작거나 같은 동일 평면 상의 점 들의 집합으로 잡는다. 영역 를
로 정의하면 가 되는데, 각각의 영역 는 두 원 의 근축으로 나뉘는 반평면 중 하나로 볼록도형이 되고 그들의 교집합 역시 볼록도형이 된다. 또한 유한개의 집합의 교집합이므로 의 경계는 반드시 유한개의 선분 혹은 반직선(근축들의 일부)이 되어야 해 증명이 끝난다.

나중에 보로노이 다이어그램(Voronoi diagram)이라는게 있다는걸 알았다. 점들이 주어져 있으면 각각의 점을 포함하는 볼록도형들로 평면을 분할할 수 있다는 내용으로 두 점 사이를 잇는 선분의 수직이등분선들로 잡는다. 즉 한 점에 대해 그 점에 이르는 거리가 다른 점에 이르는 거리보다 작거나 같은 점들의 집합을 각각의 영역으로 잡는데, 앞서 본 문제에서 모든 원들이 반지름이 0인 점원인 경우로 생각하면 일치한다. 또한 찾아보니 원래 문제에서 근축들을 이용해 그린 그림은 power diagram이라고 불리며 Laguerre-Voronoi diagram, Dirichlet cell complex 등 여러 이름으로 기존 논문들에서 등장하기도 했었다고. 정의를 그대로 두고 3차원 이상으로 일반화하는 것도 가능하다. 이와 관련된 결과 등에 대해서는 [1]을 참조.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2016/07/28)

3. 한 볼록다각형 P 내부에 n개의 원들이 있어, 어떤 두 원을 잡아도 서로 겹치지 않고 하나가 다른 하나의 내부에 있지 않았다고 한다. 이 때, P를 n개의 볼록다각형으로 분할하여 각각의 내부에 정확히 한 개의 원 전체가 들어가게 할 수 있다.

— Elegant Math (@elegant_math) July 29, 2016

References

[1] F. Aurenhammer, “Power Diagrams: Properties, Algorithms and Applications” SIAM J. Comput., 16(1), 78-96. DOI: 10.1137/0216006