1. 서 론

보로노이 다이어그램이란 공간상에 점 또는 구와 같은 기하요소가 주어져 있을 때, 전체 공간을 각각의 주어진 기하요소에 가까운 영역으로 빈틈없이 분할한 구조를 말한다. 17세기 중반 데카르트의 저서 “Principia Philosophiae”에서 보로노이 다이어그램에 대한 개념이 문헌에서 언급된 이후로 보로노이 다이어그램의 개념은 지리학, 기상학, 천문학 등의 자연과학 및 공학의 다양한 분야에서 널리 이용되고 발전되어왔다[17].

산업공학 및 경영과학 분야에서 보로노이 다이어그램은 최적 입지의 설정 문제, 차량의 경로 설정 문제, 서비스 사이트의 그룹화 문제와 같은 거리 기반의 최적화 문제를 푸는 데 효과적으로 응용되고 있다[16, 20]. 또한 보로노이 다이어그램의 형상 자체가 자연의 모습과 많이 닮아 있고 심미적으로 매우 우수하기 때문에 건축, 조형 등의 분야에도 널리 응용되고 있다[18].

공간 상에 점들이 주어져 있고 그들의 보로노이 다이어그램이 계산되어 있다면, 주어진 점들의 볼록 다각형(convex hull), 최소 걸침 나무, 최소 거리 이웃, 가브리엘 그래프 계산 등의 문제를 매우 효율적으로 풀 수 있다 [2, 17]. 그런 의미에서 보로노이 다이어그램은 단순한 하나의 문제 해결을 위한다기 보다는 주어진 기하요소의 기하학적 분석 및 추론을 위한 하나의 프레임워크로 볼 수 있다.

보로노이 다이어그램의 계산법에 대해서는 1975년 Shamos와 Hoey의 평면에서 점 집합 보로노이 다이어그램을 구성하는 O(n log n) 시간에 수행되는 효율적인 알고리듬에 대한 발표[21] 이후 다양한 방법론이 점 집합 보로노이 다이어그램을 중심으로 많은 발전이 있어 왔다. 최근에는 CGAL 등과 같은 2차원 및 3차원 공간에서 수행되는 효율적이고 안정적으로 수행되는 프로그래밍 라이브러리가 공개되어 있기 때문에 보로노이 다이어그램을 사용하기 위한 접근성은 매우 높다고 할 수 있다. 이러한 이유로 다양한 분야에서 널리 사용되고 있으며 앞으로 더욱 많은 활용이 기대된다.

보로노이 다이어그램은 대상 공간을 거리에 따라 분할하기 때문에, 거리를 어떻게 정의하느냐에 따라 다양한 변종이 발생한다. 가장 많이 사용되는 유클리드 거리부터, 각 좌표의 절대치를 더하여 정의되는 L1 거리, Hausdorff 거리 등으로 확장 가능하다. 그리고 보로노이 다이어그램을 정의하는 각 점에 가중치를 부여하여 이를 고려한 파워 거리(power distance), 가산 가중 거리(additively weighted distance), 배가 가중 거리(multiplicatively weighted distance) 등이 존재한다. 이들 중 파워 거리에 의해 정의되는 보로노이 다이어그램은 파워 다이어그램이라 하며, 가산 가중 거리에 의해 정의되는 다이어그램은 유클리드 거리에 기반한 구 집합 보로노이 다이어그램과 동일하다.

파워 다이어그램과 구 집합 보로노이 다이어그램은 최근 들어 구조 생물학 분야에서 많이 이용되고 있으며, 특히 단백질의 기하 구조를 분석하는 데 활발하게 이용되고 있다[19]. 단백질을 구성하는 원자들을 주어진 기하 요소로 보고 보로노이 다이어그램을 계산한 후 원하는 공간 해석을 수행하는 방식이 주를 이루고 있으며, 주어진 원자마다 고유의 반지름이 다르기 때문에 이들을 가중치로 보고 파워 다이어그램 또는 구 집합 보로노이 다이어그램을 구성하게 된다. 이들 다이어그램 모두 가중치를 고려하는 도구이지만 풀고자 하는 문제에 따라 정확성 및 적합성이 서로 다르게 되는 것은 자명하다.

Poupon은 보로노이 다이어그램과 파워 다이어그램이 단백질의 구조와 상호작용을 분석하는 데 응용된 최근의 연구를 리뷰 하였다[19]. 하지만 위 리뷰 논문은 두 도구가 적용된 구조생물학의 응용문제에 초점이 맞추어져 있으며, 본 논문의 주제인 두 도구의 수학적인 차이점 및 장단점에 대해서는 다루지 않고 있다. 또한 구 집합 보로노이 다이어그램은 다른 도구들보다 비교적 최근에 사용 가능하게 되었기 때문에 Poupon[19]에서 이에 대한 비중은 매우 적다.

본 논문에서는 2차원 및 3차원 공간에서 가중치를 고려하는 대표적인 도구인 보로노이 다이어그램과 파워 다이어그램을 비교해보고 이들 도구들의 장단점을 살펴본다. 특히 최근에 많은 관심을 가지고 있는 구 집합 보로노이 다이어그램에 살펴보고, 이를 통하여 구조 생물학, 재료과학, 신소재 등 구형의 입자와 관련된 분야의 사용자들이 기하학적 특성들을 분석 할 때 이들 다이어그램을 더욱 효과적으로 사용하는데 도움이 되고자 한다.

본 논문은 다음과 같이 구성되어 있다. 제 2절에서는 비교 대상 보로노이 다이어그램들의 정의 및 기본 성질에 대한 내용을 다루고, 제 3절에서는 이들의 쌍대 구조 및 컴플렉스 구조에 대해 설명한다. 제 4절에서는 응용 문제에서의 사용성을 비교한 후 제 5절에서 결론을 맺는다.

2. 보로노이 다이어그램과 파워 다이어그램

본 절에서는 비교의 대상이 되는 점 집합 보로노이 다이어그램, 구 집합 보로노이 다이어그램, 파워 다이어그램에 대한 정의와 함께 각 다이어그램의 중요한 성질에 대하여 알아본다.

2.1 점 집합 보로노이 다이어그램

d-차원 유클리드 공간에 점 집합 P = {p1, p2, …, pn}가 주어져 있다고 할 때, 점 집합 보로노이 다이어그램은 주어진 각 점에 대한 보로노이 셀(cell)의 집합으로 나타낼 수 있다. 즉, VD(P) = {VC(p1), VC(p2), …, VC(pn)}. 그리고, 각 점 pi의 보로노이 셀 VC(pi)는 다음과 같이 정의된다.

여기서 d(p, q)는 두 점 p와 q사이의 유클리드 거리(Euclidean distance)를 나타내며, 주어진 점 집합 P의 각 원소는 보로노이 다이어그램 VD(P)의 제너레이터라 부른다. 정의에 의하면 보로노이 셀 내부의 모든 점들은 해당 셀의 제너레이터와 가장 가깝다.

3차원 유클리드 공간에서 보로노이 다이어그램의 경우는 보로노이 꼭지점(vertex), 보로노이 모서리(edge), 보로노이 곡면(face), 보로노이 셀(cell)로 이루어져 있다. 보로노이 곡면은 두 개의 이웃한 보로노이 셀의 교차 면으로 정의되며, 곡면 위의 모든 점은 해당 두 개의 제너레이터들과 동일한 거리에 위치한다. 이와 비슷하게 보로노이 모서리는 세 개의 보로노이 셀과의 교차 선으로 정의되며, 보로노이 꼭지점은 네 개의 이웃한 보로노이 셀과의 교차점이 된다.

<Figure 1>(A)는 평면에서의 점 집합 보로노이 다이어그램을 나타내며, 7개의 주어진 점들은 점 집합 P를 나타낸다. 그림의 음영 영역은 제너레이터 의 보로노이 셀 VC(p)을 나타내며, VC(p)는 5개의 보로노이 곡면과 5개의 보로노이 꼭지점으로 구성되어 있다. 정의에 따라 음영 영역 내부의 모든 점에서 가장 가까운 제너레이터는 p가 된다.

2.2 구 집합 보로노이 다이어그램

보로노이 다이어그램의 제너레이터의 형상이 점에서 구(sphere)로 확장되면 보로노이 영역은 다음과 같이 정의할 수 있다.

여기에서 구의 중심은 pi 반지름은 ri라 할 때 구는 si = (pi , ri)로 나타내며, 이러한 구들의 집합을 S = {s1, s2, …, sn}와 같이 표현한다. 여기서 구 집합 S의 모든 구의 반지름이 0이 되면 구 집합 보로노이 다이어그램은 점 집합 보로노이 다이어그램과 일치하게 되며, 이러한 이유로 구 집합의 보로노이 다이어그램은 점 집합 보로노이 다이어그램의 일반화라 할 수 있다.

구 집합 보로노이 다이어그램은 주어진 구의 반지름이 커질수록 해당 제너레이터가 가지는 보로노이 셀의 영역이 커지게 되며, 구들의 반지름은 제너레이터가 가지는 상대적인 가중치 역할을 한다. 이렇듯 구 집합 보로노이 다이어그램은 각 제너레이터에 가중치를 부여할 수 있기 때문에 제너레이터의 상대적인 위치와 더불어 가중치가 중요한 의미를 가지는 응용분야에서 널리 이용되고 있다.

<Figure 1>(B)는 평면에서의 구 집합 보로노이 다이어그램을 나타내는데, 그림의 회색 원들은 평면에서의 제너레이터들을 나타내며, 원들의 중심점들은 <Figure 1>(A)의 점 집합 제너레이터들과 동일하다. 하지만 주어진 원들의 반지름이 상대적인 가중치 역할을 하게 되어 보로노이 셀에 영향을 미치게 되며, 그림에서와 같이 상대적으로 큰 반지름을 가지는 원들이 더 넓은 보로노이 셀을 가지게 된다. <Figure 1>(A)의 제너레이터 p에 대응하는 원은 주위의 제너레이터보다 상대적으로 크기가 작기 때문에 기존의 보로노이 셀보다 더 좁은 영역을 확보하고 있으며, 셀의 경계를 구성하고 있는 보로노이 곡면의 개수는 하나 줄어들어 있다.

3차원의 경우 구 집합 보로노이 다이어그램의 보로노이 면은 두 구와 동일한 거리에 위치한 점들의 자취가 되며 이는 쌍곡면(two-sheet hyperboloid) 의 일부가 된다. 구 집합 보로노이 다이어그램의 위상 및 기하 정보 및 알고리듬에 대한 자세한 내용은 참고문헌[10, 11, 13, 14]을 참고하기 바란다.

2.3 파워 다이어그램

파워 다이어그램은 Aurenhammer의 발표[1] 이후 공간 상의 주어진 기하요소들 간의 근접성(proximity)을 분석하는데 많이 이용되고 있다. 라구에르(Laguerre) 다이어그램이란 이름으로도 알려져 있는 파워 다이어그램은 주어진 점들의 위치뿐만 아니라 가중치라는 부가적인 속성이 중요한 의미가 있는 문제에서 점 집합 보로노이 다이어그램보다 더욱 효과적으로 응용될 수 있다.

점 집합 보로노이 다이어그램과 구 집합 보로노이 다이어그램이 유클리드 거리에 기반하는 것과는 다르게 파워 다이어그램은 다음과 같이 정의되는 파워 거리(power distance)에 기반하고 있다.

여기서 파워 거리가 정의되기 위해서는 각 제너레이터 마다 가중치(weight)가 주어져 있어야 하며 기호로 로 나타낸다. 그리고 파워 다이어그램에서 제너레이터 의 영역 는 파워 셀(power cell) 이라 부르며 다음과 같이 정의된다.

위의 식에서 알 수 있듯이 파워 다이어그램은 모든 제너레이터의 가중치 가 0인 경우 다이어그램을 정의하는 거리가 가중치가 없는 유클리드 거리만의 제곱이 되어 점 집합 보로노이 다이어그램과 같아진다. 그래서 파워 다이어그램 또한 구 집합 보로노이 다이어그램과 함께 점 집합 보로노이 다이어그램의 일반화라 할 수 있다.

<Figure 1>(C)에서와 같이 파워 다이어그램의 모서리 및 면은 점 집합의 보로노이 다이어그램과 같이 선형을 이루고 있다. 파워 다이어그램도 구 집합 보로노이 다이어그램과 같이 제너레이터의 가중치가 클 수록 상대적으로 더 넓은 파워 셀을 가진다. 이렇듯 파워 다이어그램은 제너레이터의 가중치를 반영하면서도 비교적 다루기 쉬운 구조인 선형의 위상 요소를 가지는 장점을 가진다.

그러나 두 다이어그램의 사용자 측면에서는 파워 거리 보다 유클리드 거리가 더욱 익숙하기 때문에 파워 다이어그램이 비록 가중치의 차이를 반영하고 있기는 하나 직관성은 높지 않다고 할 수 있다. 또한 <Figure 1>(A)의 제너레이터 p에 대응하는 파워 셀의 경우처럼, 파워 다이어그램의 경우 파워 셀은 해당 제너레이터의 중심점을 포함하고 있지 않을 수도 있으며, 이는 구로 표현된 원자들의 공간을 분석 할 경우 화학적으로 합리적인 표현이라 할 수 없다[9]. 참고로 구 집합 보로노이 다이어그램의 경우 보로노이 셀은 해당 제너레이터의 중심점을 항상 포함하고 있다.

<Figure 1>(A)와 <Figure 1>(C)를 비교해 보면, 점 집합 보로노이 다이어그램의 모서리들의 연결 관계와 파워 다이어그램의 연결 관계가 본 예제의 경우 동일하다는 것을 알 수 있다. 그림에서와 같이 주어진 제너레이터의 반지름 차이가 많이 남에도 불구하고, 가중치가 없는 점 집합 보로노이 다이어그램과 같다는 것은 가중치가 파워 다이어그램에 미치는 영향이 구 집합 보로노이 다이어그램보다 상대적으로 적다고 말할 수 있다.

파워 다이어그램의 제너레이터 는 중심이 이고 반지름 인 구로 표현이 가능하다. 다시 말하면 각 제너레이터의 가중치는 해당 구 반지름의 제곱이 된다. 그래서 파워 거리 는 <Figure 2>(B)에서와 같이 점 에서부터 구 까지의 접선 거리의 제곱과 같다. 파워 거리는 기본적으로 유클리드 거리의 제곱을 사용하고, 중심까지의 최단 거리가 아니라 접선 거리와 관계하기 때문에 사용자의 입장에서 일반적이고 익숙한 유클리드 거리 보다는 직관적이지 않다는 단점을 가지고 있다.

3. 쌍대 구조와 컴플렉스 구조

각각의 보로노이 다이어그램은 대응하는 쌍대 구조(dual structure)를 가지고 있으며, 이러한 쌍대 구조 또한 다양한 응용분야에서 활발하게 이용되고 있다. 점 집합 보로노이 다이어그램의 쌍대 구조는 딜러니 삼각화(Delaunay triangulation)로 널리 알려져 있으며, 구 집합 보로노이 다이어그램의 쌍대 구조는 쿼지 삼각화(quasi-triangulation)로 알려져 있다. 그리고 파워 다이어그램의 경우는 레귤러 삼각화(regular triangulation)로 알려져 있다.

3.1 쌍대 구조

3차원의 경우 쌍대 구조는 다음과 같이 정의할 수 있다. 쌍대 구조는 보로노이 다이어그램을 계산한 후 각각의 보로노이 곡면을 정의하는 두 개의 제너레이터로 모서리 심플렉스(edge simplex)를, 각각의 보로노이 모서리를 정의하는 세 개의 제너레이터로 삼각형 심플렉스(triangular simplex)를, 각각의 보로노이 꼭지점을 정의하는 네 개의 제너레이터로 사면체 심플렉스(tetrahedral simplex)를 구성하여 만들어진다. 일반차원의 경우 모서리, 삼각형, 사면체 심플렉스는 해당 심플렉스가 놓인 차원의 의미로 각각 1-심플렉스, 2-심플렉스, 3-심플렉스로 불려진다. 그리고 보로노이 구조와 쌍대 구조는 상호 쌍대 관계를 가지며, 특히 위상(topology) 정보의 경우 하나를 구하면 다른 하나의 구조는 단순한 위상 연산 만으로 쉽게 구해진다.

<Figure 3>(A)는 점 집합 보로노이 다이어그램의 쌍대 구조를 보여주고 있으며, 단순히 각각의 보로노이 모서리를 정의하는 두 개의 제너레이터를 이은 선분을 만들어서 쌍대 구조를 얻을 수 있음을 확인할 수 있다. 점 집합 보로노이 다이어그램의 쌍대 구조는 딜러니 삼각화라는 이름으로 매우 잘 알려져 있다. 점 집합이 주어져 있을 때 딜러니 삼각화는 여러 가능한 삼각화 방법들 중 정삼각형에 가까운 삼각형들로 삼각화를 구성하며, 이러한 좋은 성질 때문에 컴퓨터 그래픽스에서 메시(mesh) 생성, 역 설계 및 역 공학에서의 곡면 재생성(surface reconstruction), GIS에서 지형 데이터의 생성, 기계 해석 분야에서 유한 요소법(FEM) 등과 같은 많은 응용분야에서 널리 사용되고 있다[17].

파워 다이어그램의 쌍대 구조는 레귤러 삼각화라는 이름으로 알려져 있다. 레귤러 삼각화는 딜러니 삼각화와 마찬가지로 주어진 점 집합의 볼록 다각형(convex hull) 내부를 삼각화 한다. 그리고 파워 다이어그램과 같이 주어진 점의 위치와 함께 가중치에 의해 정의된다. 가중치가 상대적으로 클수록 해당 제너레이터(꼭지점)에 인접한 모서리의 개수가 증가하게 된다. 참고로 파워 다이어그램은 가중치가 커질수록 셀의 면적 및 부피가 늘어나게 되며 셀의 외곽을 구성하는 위상 요소의 개수도 증가하게 된다.

딜러니 삼각화와 레귤러 삼각화 모두 심플리셜 컴플렉스(simplicial complex)를 이루고 있다. 심플리셜 컴플렉스 K란 다음의 두 가지 조건을 만족하는 심플렉스 집합을 말한다[3]. 1. K의 심플렉스를 구성하는 면(face) 역시 K에 속하고, 2. 두 심플렉스가 교차한다면 교차 면도 K에 속한다. 일반적으로 삼각화(triangulation or tetrahedralization)는 이러한 조건을 만족하기 때문에 심플리셜 컴플렉스라 할 수 있다.

그러나 구 집합 보로노이 다이어그램의 쌍대 구조는 심플리셜 컴플렉스의 조건을 대부분의 영역에서 만족하고 있지만 그렇지 못하는 부분도 일부에서 존재한다. 이를 아노말리(anomaly)라는 용어로 설명하고 있으며, 쌍대 구조 대부분에서 삼각화를 이루고 있기 때문에 쿼지(quasi) 삼각화란 이름으로 통용되고 있다. 이에 대한 자세한 내용은 참고문헌 [12]을 참조하기 바란다.

3.2 컴플렉스 구조

점 집합 보로노이 다이어그램, 구 집합 보로노이 다이어그램, 파워 다이어그램의 컴플렉스 구조는 각각 알파 컴플렉스(alpha-complex), 베타 컴플렉스(beta-complex), 가중치 알파 컴플렉스(weighted alpha-complex)로 알려져 있으며, 보로노이 다이어그램에서와 마찬가지로 베타 컴플렉스와 가중치 알파 컴플렉스는 모두 알파 컴플렉스의 일반화이다. 제너레이터들의 가중치가 모두 0으로 동일하다면 모두 알파 컴플렉스로 수렴한다.

보로노이 다이어그램의 쌍대 구조인 딜러니 삼각화, 쿼지 삼각화, 레귤러 삼각화의 일부분이 컴플렉스 구조를 구성하며, d-차원 공간에서 보로노이 다이어그램의 쌍대 구조는 0-, 1-, …, d-심플렉스의 집합으로 구성되어 있다. 3차원의 경우 꼭지점, 모서리, 삼각형, 사면체의 집합으로 이루어져 있다. 컴플렉스 구조는 이들 쌍대 구조를 구성하는 심플렉스들의 부분 집합으로 구성되어 있다 [5, 8].

컴플렉스 구조는 쌍대 구조의 부분 집합이며, 반지름을 의미하는 하나의 실수 값 파라미터를 추가하여 사용성을 높인 구조라 할 수 있다. 2차원 평면에서 점 집합의 컴플렉스 구조를 예로 들면, 파라미터 값을 라 하고 딜러니 삼각화를 구성하는 각각의 삼각형에 대하여, 삼각형의 세 꼭지점들을 지나는 원을 정의할 수 있는데 이 원의 반지름이 주어진 파라미터 보다 작다면 해당 삼각형은 컴플렉스 구조의 삼각형 심플렉스 집합의 멤버가 되고 삼각형을 이루는 모서리 또한 컴플렉스의 멤버가 된다. 그리고 나머지 모서리들에 대해서 해당 모서리를 지름으로 하는 원을 생각할 수 있는데 이 원의 반지름이 보다 작으면 해당 모서리는 컴플렉스 구조의 멤버가 된다. 이러한 방식으로 만들어진 컴플렉스 구조를 알파 컴플렉스라 하며 심플리셜 컴플렉스의 조건을 만족한다.

베타 컴플렉스(beta-complex)도 위와 비슷한 방식으로 구성할 수 있다. 알파 컴플렉스와 마찬가지로 반지름을 의미하는 파라미터는 기호 로 구분한다. 이 경우 쌍대 구조는 쿼지 삼각화가 되며, 세 점을 지나는 원의 경우는 세 원에 동시에 외접하는 구와 대응되고, 모서리를 지름으로 하는 원의 경우는 두 원에 동시에 외접하는 원과 대응된다. 그리고 이러한 외접 구의 반지름을 값과 비교하여 보다 작으면 컴플렉스 구조의 심플렉스로 남겨두는 방식으로 구성할 수 있다.

파워 다이어그램의 컴플렉스 구조인 가중치 알파 컴플렉스(weighted alpha-complex) 또한 유사한 방식으로 구성 가능하다. 이 경우도 반지름을 의미하는 파라미터 가 필요하며, 쌍대 구조인 레귤러 삼각화에서 시작하여 각 심플렉스가 컴플렉스 구조의 멤버가 되는지를 검사하는 방식으로 구성한다. 그러나 가중치 알파 컴플렉스는 파워 거리에 기반한 구조이기 때문에 레귤러 삼각화의 삼각형이 주어진다면, 해당 세 제너레이터들의 외접원을 구하는 것이 아니라 파워 거리가 같은 점을 찾고 그때의 파워 거리와 를 비교하여 컴플렉스 구조를 구성한다. 이 경우 해당 점을 중심으로 하고 파워 거리의 제곱근을 반지름으로 하는 원을 생각할 수 있는데, 이 원은 세 제너레이터들과 동시에 수직으로 교차하는 성질을 가지고 있다.

3.2.1 컴플렉스 구조의 기하학적 의미

2차원 평면에 베타 컴플렉스가 주어져 있다고 할 때, 두 원 사이에 모서리가 정의되어 있다는 의미는 반지름 의 원형 프로브(probe)가 해당 두 원에 동시에 접할 수 있다는 의미이다. 다시 말하면 이 두 구 사이에는 프로브가 교차 없이 통과 할 수 없다는 의미이다. 참고로 프로브는 제너레이터의 경계에서만 접할 수 있으며 교차할 수는 없다. 그리고 베타 컴플렉스에 삼각형 심플렉스가 정의되어 있다면 세 제너레이터 사이에는 프로브가 놓일 수 없다는 것을 의미한다. 이러한 개념은 3차원으로 동일한 과정을 통해 확장할 수 있다. 그리고 알파 컴플렉스의 경우는 주어진 제너레이터가 점 집합이란 것을 제외하고는 베타 컴플렉스와 동일하다.

베타 컴플렉스가 주어져 있다면 프로브가 지나다닐 수 있는 영역은 베타 컴플렉스가 정의되어 있지 않은 영역이 된다. 이 말은 거꾸로 쌍대 구조에서 베타 컴플렉스를 이루지 않는 심플렉스에 프로브가 자유롭게 다닐 수 있다는 것을 의미한다. 이러한 특성은 주어진 구 집합의 빈 공간을 탐색하는 문제, 특정 반지름의 프로브가 내부를 통과할 수 있는 경로를 찾는 문제 등에 적용 가능하다. 가중치 알파 컴플렉스도 유사한 방식으로 적용 가능하나 프로브가 의미하는 바가 제너레이터에 접하는 것이 아닌 제너레이터에 수직으로 교차하는 것과 대응한다. 이러한 점은 가중치 알파 컴플렉스를 사용하는 데 있어서 파라미터 값의 결정과 같은 기하학적 직관을 가지기 어렵게 만든다.

4. 응용문제에서의 사용성 비교

구 집합 보로노이 다이어그램과 파워 다이어그램은 2차원 및 3차원에서 구형 입자들의 공간 추론과 관련된 문제에 널리 이용되고 있다. 특히 원자를 구로 모델링 할 때, 분자 및 재료의 공간 분포에 대한 특성 분석에 큰 장점을 가지고 있다. 본 절에서는 이러한 다이어그램이 이용되는 몇 가지 상황을 살펴보고 상황 별 적합성을 비교해 본다.

<Figure 4>는 보로노이 다이어그램을 이용하여 단백질 특성을 분석하는 사례를 보여주고 있다. <Figure 4>(A)는 1665개의 원자로 이루어진 단백질 모델(pdb code : 1ajx)을 보여주고 있다. 본 단백질은 세 개의 원자 그룹으로 구성되어 있는데 <Figure 4>(B)는 이러한 원자 그룹이 어떠한 위치에서 어떠한 기하학적 형태로 상호작용 하고 있는지를 분석한 예인데, 가운데 부분의 구겨진 종이 모양의 면은 보로노이 곡면의 일부로 정의하였다. <Figure 4>(C)는 같은 단백질에서 안으로 움푹 들어가 있는 영역인 포켓을 보여주고 있으며, 이는 단백질의 특성 분석 및 신약 개발 등에서 매우 중요한 문제로 알려져 있다.

4.1 최단거리 이웃(Nearest Neighbor) 탐색

공간 상에 구들이 주어져 있을 때, 이 들 간에 최단 거리에 있는 이웃을 찾는 것은 가장 기본이 되는 연산 중 하나이기 때문에 중요한 의미를 가진다. 구 집합 보로노이 다이어그램은 구들간의 가장 가까운 쌍에 대해서는 두 구 사이에 보로노이 곡면을 항상 가지고 있다 [17]. 이를 쌍대 구조로 설명하면 가장 가까운 두 구 사이에는 항상 모서리(1-심플렉스)가 형성되어 있다. 그러나 이러한 특성은 파워 다이어그램의 경우 항상 성립하는 것은 아니다. 파워 다이어그램의 쌍대 구조인 레귤러 삼각화에서는 공간상의 점에서 두 구까지 파워 거리의 합이 최소인 쌍에 대해서는 쌍대 구조의 모서리를 형성하고 있지만, 이것이 구들 사이의 최소 유클리드 거리를 의미하는 것은 아니다. 그러므로 응용문제 중 최단거리 쌍을 구해야 하는 상황이 발생하는 경우 구 집합 보로노이 다이어그램은 정확한 해를 주지만 파워 다이어그램은 그렇지 않으며, 만약 파워 다이어그램을 사용해야만 한다면 이를 통해서는 근사해를 얻을 수 있을 것이다. 이는 다음과 같이 정리할 수 있다.

Claim 1 구 집합 S에 대하여 S의 쿼지 삼각화 모서리를 이용하면 최단거리의 이웃 제너레이터를 찾을 수 있지만, S의 레귤러 삼각화의 모서리를 통해서는 항상 찾을 수 있는 것은 아니다.

4.2 구들 간의 교차 여부

구 집합 보로노이 다이어그램과 파워 다이어그램은 모두 제너레이터들이 교차하는 경우 교차 여부를 정확하게 확인 가능하다. <Figure 1>(B)와 <Figure 1>(C)에서 볼 수 있듯이 교차하는 제너레이터들 사이의 보로노이 모서리는 제너레이터 경계의 교차점을 정확하게 지난다는 것을 확인할 수 있다. 3차원의 경우도 파워 다이어그램 및 보로노이 곡면은 제너레이터가 교차한다면 교차선(원호를 이룸)을 정확히 지나게 된다. 그래서 보로노이 다이어그램의 이용 목적이 교차여부를 확인하는 것이라면 두 다이어그램 모두 적합한 도구라 할 수 있다.

Claim 2 구 집합 S에 대하여 보로노이 다이어그램과 파워 다이어그램 모두에서 두 제너레이터가 교차하면서 교차지점이 구들 합집합의 경계에 놓일 경우 두 제너레이터 사이에는 보로노이 곡면이 생성된다.

4.3 병목 지점 탐색

구 집합 S가 주어져 있을 때 구형의 프로브가 S의 구들을 교차하지 않으면서 구들의 볼록 다각형과 같은 구역 내부를 통과하는 경로를 생각할 수 있다. 이러한 조건을 만족하는 경로는 다수가 있을 수 있는데, 병목(bottleneck)이라 함은 각각의 경로에 대하여 통과 가능한 최대 반지름의 프로브가 결정되는 위치 및 그때의 반지름을 의미한다. 즉, 각 경로 별 가장 좁은 위치를 찾는 것을 의미한다.

구 집합 보로노이 다이어그램의 각각의 모서리에서 그 위치의 지역적인 병목을 정확하게 계산할 수 있으며, 이러한 병목 정보가 계산된 모서리와 꼭지점은 다양한 형태의 경로를 찾기 위한 입력 그래프의 역할을 할 수 있다. 이렇게 그래프가 주어지고 Dijkstra의 최단경로탐색 알고리듬 등의 경로 탐색 방법론을 적용하면 최단 경로, 최대 병목 경로, 최장 경로 등 다양한 경로를 찾을 수 있다. 그러나 파워 다이어그램의 모서리를 통해서는 최소 유클리드 거리가 아닌 최소 파워 거리를 알 수 있으며 이것이 병목의 역할을 할 수는 있다. 그러나 이는 프로브가 제너레이터와 직각으로 교차한 경우이기 때문에 교차 없이 통과 가능한 반지름을 찾는 것은 파워 다이어그램만으로는 쉽지 않다.

Claim 3 구 집합 S에 대하여 보로노이 다이어그램을 통해서 특정 반지름을 가지는 구가 S의 구와 교차 없이 통과 가능한지의 여부를 정확하게 판단할 수 있다.

4.4 내부 빈 공간 탐색

병목 지점의 탐색과 유사하게 구 집합 보로노이 다이어그램에서는 내부 빈 공간의 탐색도 가능하다. 내부 빈 공간이란 특정 반지름을 가지는 프로브가 구 집합 내부에 존재하면서 구들과 교차하지 않고는 바깥으로 빠져 나갈 수 없는 영역을 말한다. 2차원 평면을 예로 든다면 베타 컴플렉스가 내부에 삼각형들로 채워져 있지 않은 아일랜드를 가지고 있다면 이 영역에 반지름 베타의 프로브가 놓일 수 있다는 것을 의미하며, 베타 컴플렉스는 이러한 영역을 빠짐 없이 정확하게 찾아준다. 그리고 쿼지 삼각화가 주어져 있을 때, 베타 값을 변경하여 다양한 크기의 빈 공간을 정확하게 찾을 수 있으며, 베타 값을 통해 빈 공간의 적당한 크기를 조절할 수 있는 장점이 있다.

파워 다이어그램을 통해서도 위의 아일랜드를 찾는 방법론을 적용하여 효율적으로 빈 공간을 찾을 수 있다. 그러나 베타 컴플렉스의 베타 값 조절에서와 같이 알파 값을 조절을 통해서는 해당 프로브가 교차 없이 해당 공간에 놓여질 수 있는지, 주어진 구들과 교차 없이 빠져 나갈 수 있는지의 여부를 판단하는 것은 쉽지 않다.

4.5 구들 간의 합집합 계산

구들 간의 합집합이란 구들이 공간에 차지하고 있는 영역의 합집합을 의미하며, 구들 합집합의 계산이란 부피와 겉넓이 모두가 대상이 된다. 이러한 계산을 통해서 구 집합이 차지하고 있는 밀도 등을 정확히 계산할 수 있다. 특히 분자생물학에서 이러한 계산은 해당 분자가 가지고 있는 에너지의 계산 등에 유용한 것으로 알려져 있다[7].

Edelsbrunner는 가중치 알파 컴플렉스의 심플렉스들을 이용하여 단순 inclusion-exclusion 공식(구들 각각의 부피를 더한 후 중복된 영역을 빼는 과정을 통해 합집합을 구하는 방식)을 적용하여 합집합 부피를 효율적으로 계산하는 알고리듬을 발표하였다[6]. 이는 파워다이어그램 및 컴플렉스구조가 구들의 교차정보에 대해서는 정확한 정보를 주기 때문인 것으로 판단된다. Kim 등은 베타 컴플렉스를 이용하여 합집합 부피와 겉넓이를 효율적으로 계산하는 알고리듬을 발표하였다[15]. 베타 컴플렉스의 정보를 이용하여 합집합 영역을 기본 부피 단위로 분할하고 각각 부피를 계산한 후 합하는 방식을 취하였다.

여기서 주어진 구들의 합집합을 구한 후 모든 구들에 대해 반지름을 동일하게 증가시킨 후 합집합을 구하는 상황을 생각해보자. 구 집합 보로노이 다이어그램의 경우 베타 컴플렉스의 베타 값만 변경하여 동일한 작업을 적용하면 쉽게 계산할 수 있으나, 파워 다이어그램의 경우는 가중치 알파 컴플렉스의 알파 값을 변경하면 모든 제너레이터마다 동일한 크기만큼 증가하지 않는다. 그렇기 때문에 동일하게 반지름을 증가시킨 후 새로운 파워 다이어그램을 구하고 가중치 알파 컴플렉스를 구하여 합집합을 구해야 한다. 이러한 상황에서는 구 집합 보로노이 다이어그램과 베타 컴플렉스가 계산량에 있어서 더욱 유리하다고 할 수 있다.

Claim 4 구 집합 S가 있을 때 반지름이 동일한 크기만큼 증가 또는 감소하는 상황에서의 보로노이 다이어그램은 S의 보로노이 다이어그램과 동일하나, 파워 다이어그램은 S의 파워 다이어그램과 항상 동일한 것은 아니다.

5. 결 론

점 집합 보로노이 다이어그램은 공간에 점들이 주어져 있을 때, 이들의 기하학적인 관계를 파악하고 분석하는데 중요한 역할을 해왔으며 지금도 다양한 응용분야에서 활발히 이용되고 있다. 구 집합의 보로노이 다이어그램과 파워 다이어그램은 주어진 점들 각각에 가중치를 적용한 구조로 볼 수 있으며, 가중치가 중요한 의미가 있는 단백질의 공간 구조 분석, 재료의 특성 분석과 같은 응용 문제에 더욱 효과적으로 적용되었다. 구 집합 보로노이 다이어그램은 주어진 가중치를 구의 반지름으로 두고 유클리드 거리에 의해 정의되는 반면, 파워 다이어그램은 주어진 가중치의 제곱근을 구의 반지름으로 두고, 접선 거리의 제곱인 파워 거리에 기반하여 정의되기 때문에 두 구조의 사용성 및 직관성에는 적지 않은 차이가 있다. 본 논문에서는 점 집합 보로노이 다이어그램, 구 집합 보로노이 다이어그램, 파워 다이어그램의 정의와 성질을 살펴보고 이들의 강점을 응용문제에서 발생하는 다양한 상황에 대하여 사용자 측면에서 고찰해 보았다.

점 집합 보로노이 다이어그램과 파워 다이어그램은 보로노이 곡면이 선형이며, 쌍대 구조가 삼각화를 이룬다는 장점이 있다. 파워 다이어그램과 구 집합 보로노이 다이어그램 모두 구들이 서로 교차하는 상황에 대해서는 교차에 대한 정확한 정보를 얻을 수 있었다. 그러나 구들이 서로 떨어져 있는 경우나 최단 거리 이웃, 병목 지점, 내부 빈 공간 탐색과 같이 거리에 대한 정확성을 요구하는 상황에서는 구 집합 보로노이 다이어그램이 더욱 효율적이며 효과적이라는 결론을 얻을 수 있었다.

Acknowledgements

This work was supported by the Korea Research Foundation Grant funded by Korean Government(KRF-2008-521-D00545).