생소한 이름이지만, 공학이나 생물학, 지리학, 건축과 예술까지 여러 분야에 쓰이고 있다. 다양한 분야에서 보로노이 다이어그램이 어떻게 쓰이고 있는지 알아보자.
보로노이 다이어그램이란?
‘보로노이 다이어그램’은 1868년 우크라이나에서 태어난 러시아의 수학자 조지 보로노이의 이름을 따서 그 이름을 지었다. 똑같지 않은 다각형으로 채워져 있어 규칙이 없는 것처럼 보이지만, 수학적인 원리로 평면을 분할하는 과정에서 나타나는 그림이다.
보로노이 다이어그램을 그리는 방법은 간단하다. 먼저 평면 위에 여러 개의 점을 찍는다. 그런 다음, 가장 인접한 두 개의 점을 선택해 수직이등분선을 그리면 평면은 수직이등분선에 의해 여러 개의 다각형으로 분할된다.
이렇게 그려진 그림을 보로노이 다이어그램이라고 하고, 이때 생기는 다각형을 보로노이 다각형이라고 한다. 보로노이 다각형은 특정 점을 기준으로 가장 가까운 점들을 모은 집합이 된다. 이것이 보로노이 다이어그램이 갖는 가장 중요한 성질이다. 보로노이 다각형의 모서리는 로봇이나 GPS 등 최단경로를 찾는 데에 종종 쓰인다.
보로노이 다이어그램을 그리다 보면 아래 그림❶과 같이 인접한 점을 연결해 그려지는 삼각형을 발견할 수 있다. 이들 삼각형도 보로노이 다각형과 마찬가지로 평면을 분할하는데, 이러한 분할을 ‘델로네 삼각분할’이라고 한다. 델로네 삼각형의 외심은 보로노이 다각형의 꼭짓점이 된다.
보로노이 다이어그램과 델로네 삼각분할은 서로 쌍대관계를 갖는다. 이 때문에 보로노이 다이어그램을 알면 델로네 삼각형을, 델로네 삼각형을 알면 보로노이 다이어그램을 그릴 수 있다.
한편 2차원 평면에서 그린 보로노이 다이어그램을 3차원 공간에서 그리는 것도 가능하다. 이때는 수직이등분선 대신에 수직이등분평면으로 공간을 분할한다. 그러면 그림❷와 같은 3차원 보로노이 다이어그램이 완성된다.
공공기관의 관할구역을 효율적으로 나누는 방법은?
우리가 살고 있는 동네에는 소방서, 동사무소, 경찰서와 같이 국민들의 편의를 위한 여러 종류의 공공기관이 있다. 이런 공공기관은 국민들의 편의를 위해 지어진 것으로 누구나 접근하기 편리한 곳에 있어야 한다. 그러려면 그 지역의 사람들을 빠짐없이 나누면서도, 각 사람들이 가장 가깝고 편리하게 접근하도록 공공기관의 관할구역을 나눠야 한다. 이와 같이 어떤 지역의 공간을 효율적으로 나누는 문제를 ‘분할 문제’라고 한다. 이런 문제는 지리학자들의 연구 분야 중 하나로, 지리학자들은 분할 문제를 해결하기 위해 많은 노력을 기울이고 있다.
공공기관의 관할구역 분할 문제를 해결하는 데 보로노이 다이어그램은 핵심적인 역할을 한다. 그 이유는 보로노이 다이어그램이 특정한 점을 기준으로 가장 가까이에 있는 점들로 공간을 나눈다는 성질이 있기 때문이다. 공공기관을 점으로 생각해 보로노이 다이어그램을 그리면, 보로노이 다각형이 바로 공공기관의 관할 구역이 된다.
그러나 현실에 적용할 효율적인 관할구역을 찾는 데에는 보로노이 다이어그램만으로는 부족하다. 보로노이 다이어그램은 *유클리드 거리만을 고려해 분할한 것이기 때문이다. 실제 지역에서는 유클리드 거리가 최선의 방법이 아닌 경우가 무척 많다. 출발점과 도착점 사이에 산이나 강이 있다거나, 도로가 없는 경우에 유클리드 거리는 가장 짧은 길이 아니다. 따라서 현실에서 적용할 수 있는 최선의 관할구역을 찾으려면 보로노이 다이어그램은 기본이고 지역의 지형이나 인구밀도, 도로의 상황까지도 고려해야 한다.
하지만 보로노이 다이어그램이 모든 분할 문제에 쓰이는 것은 아니다. 공공 기관이 아닌 편의점이나 패스트푸드와 같은 가게는 공익을 목적으로 하지 않고, 높은 이윤을 목적으로 한다. 이 때문에 모든 사람이 아닌 주요 소비층만을 대상으로 해서 위치를 정한다. 따라서 상점의 위치를 정하는 문제에는 보로노이 다이어그램을 적용하지 않는다.
*유클리드 거리
두 점 A와 B사이의 거리는 두 점을 잇는 선분의 길이로 구하는 것을 유클리드 거리라고 한다. 일반적으로 사람들이 알고 있는 거리를 뜻한다.
우리동네 소방서의 관할구역, 효율적일까?
우리동네 소방서의 관할구역은 효율적으로 나눠져 있을까? 보로노이 다이어그램을 이용하면 공간의 분할이 효율적으로 이뤄졌는지 확인할 수 있다. 실제로 2007년 지리학회 학술발표에는 보로노이 다이어그램을 이용해 서울 한 지역의 소방서 관할구역이 효율적인지 아닌지를 분석하는 연구가 발표됐다. 이 연구는 당시 대원외고 3학년에 재학중인 학생들의 연구여서 더욱 주목을 받았다.
1. 연구 목표
보로노이 다이어그램을 활용해 소방서의 관할구역을 분석하고, 효율적인 관할구역을 찾는다.
2. 연구 방법
서울 서초구, 강남구, 송파구의 소방파출소 22개를 대상으로, 각 소방서의 관할구역을 다음과 같이 3가지 방법으로 나눠 보았다.
➊ 공급데이터를 고려한 관할구역 - 소방서마다 출동할 수 있는 출동양이 다르므로 소방서가 공급할 수 있는 출동양을 고려해 분할했다.
➋ 수요데이터를 고려한 관할구역 - 지역마다 화재가 일어나는 빈도가 다르므로, 소방 대상물의 수를 고려해 분할했다.
➌ 도로망을 고려한 관할구역 - 도로망을 고려해 관할구역을 분할했다.
▶ ➊, ➋는 유클리드 거리함수에 각각 공급데이터와 수요데이터를 가중치로 두고 계산했고, ➌은 유클리드 거리가 아닌 네트워크에 기반을 둔 거리를 이용해 관할구역을 계산했다.
3. 연구 결과
그림➎ : 수요데이터 고려
그림➏ : 도로망 고려
프로그램을 이용해 세 가지 관할구역을 계산한 결과는 그림➍~➏과 같았으며, 이 중에서 가장 효율적인 분할은 도로망을 고려한 관할구역이었다.
그리고 실제 소방서의 관할구역과 비교해 본 결과, 실제 소방서의 관할구역은 행정상의 편의를 위해 나눠져 있을 뿐, 효율적인 분배라고 보기는 어려웠다.
보로노이 다이어그램, 건축에도 쓰인다!
보로노이 다이어그램은 세포의 분열이나 동물의 무늬, 벌집과 같이 다양한 자연 구조와 닮아 예술적인 가치도 높다. 자연의 패턴이나 구조는 완전하며 아름다운 균형미를 가지고 있기 때문이다. 게다가 보로노이 다이어그램은 공간 분할에 있어서도 최소를 이용해 최대한의 효과를 얻는 원리를 담고 있어 경제적이기도 하다.
예술성과 경제성을 두루 갖추고 있는 보로노이 다이어그램은 건축 디자인에서도 자주 활용된다. 보로노이 다이어그램을 활용한 건축에는 어떤 것이 있을까?
단백질 구조와 로봇 경로 찾아내는 보로노이 다이어그램!
일상생활의 편리와 아름다움을 넘어 보이지 않는 세포나 분자와 같은 작은 자연의 세계를 이해하는 데에도 보로노이 다이어그램이 쓰이고 있다.
예를 들어 보로노이 다이어그램을 이용하면 단백질 구조를 정확하게 알 수 있다. 분자를 이루고 있는 원자의 중심에 점을 찍어 보로노이 다이어그램을 그리면, 이를 토대로 분자의 구조를 계산할 수 있다.
특히 과거에는 2차원 보로노이 다이어그램을 이용했지만, 현재는 3차원 보로노이 다이어그램을 이용해 단백질 구조를 더 정확하게 구할 수 있다. 2차원 보로노이 다이어그램을 이용할 때는 분자를 이루고 있는 서로 다른 원자의 크기를 고려하는 것이 어려웠다. 점을 선택해 그린 보로노이 다이어그램이 평면적이기 때문에, 분자의 구조를 정확하게 알 수 없었던 것이다. 그러나 3차원 보로노이 다이어그램을 그리면, 분자의 입체 모양을 정확하게 알 수 있다. 그 결과 같은 분자처럼 보이는 것도 거리와 위치를 파악해 서로 다른 분자로 구별할 수 있게 됐다.
보로노이 다이어그램은 로봇의 경로를 찾는 데에도 쓰인다. 로봇이 장애물을 만나면 피해가도록 동선을 짜는 것이 필요한데, 보로노이 다이어그램은 이런 문제를 해결하는 데 핵심적인 역할을 한다. 보노로이 다각형의 모서리가 분할된 공간에서 최단 경로 역할을 한다는 점을 이용한 것이다.
이처럼 보로노이 다이어그램은 생활 속 곳곳에서부터 첨단 연구까지 무척 다양한 곳에서 활약하고 있다. 보로노이 다이어그램이야 말로 진정한 멀티플레이어가 아닐까?
