파워 다이어그램

계산기하학에서 파워 다이어그램()은 라게르-보로노이 다이어그램(), 디리클레 셀 복합체(), 기저 보로노이 테셀레이션() 또는 단면 디리클레 테셀레이션()이라고도 불리며, 원의 집합으로부터 정의된 다각형 셀로 평면을 분할한 것이다. 주어진 원 C에 대한 셀은 C에 대한 방멱 거리가 다른 원들에 대한 방멱 거리보다 작은 모든 점들로 구성된다. 파워 다이어그램은 일반화된 보로노이 다이어그램의 한 형태이며, 모든 원의 반지름이 같을 경우 원 중심의 보로노이 다이어그램과 일치한다.....

 정의 
섬네일|주어진 원 밖에 있는 점 P의 방멱
C가 원이고 P가 C 밖에 있는 점일 때, C에 대한 P의 방멱은 P에서 C의 접점 T까지의 선분 길이의 제곱이다. 동등하게, P가 원의 중심에서 거리 d에 있고 원의 반지름이 r이라면, (피타고라스 정리에 따라) 방멱은 d2 − r2이다. 이 동일한 공식 d2 − r2은 C 안에 있든 밖에 있든 평면의 모든 점에 대해 확장될 수 있다: C 위의 점은 방멱이 0이고, C 안의 점은 음의 방멱을 가진다.

n개의 원 Ci 집합의 파워 다이어그램은 평면을 n개의 영역 Ri (셀이라고 함)로 분할한 것으로, 원 Ci가 P의 방멱을 최소화하는 원일 때 점 P는 Ri에 속한다.

섬네일|두 교차하는 원의 근축. 두 원의 파워 다이어그램은 이 선으로 형성된 두 반평면으로 평면을 분할한 것이다.
n = 2인 경우, 파워 다이어그램은 두 원의 근축 또는 코르달(chordale)이라고 불리는 선으로 분리된 두 개의 반평면으로 구성된다. 근축을 따라 두 원은 동일한 방멱을 가진다. 더 일반적으로, 모든 파워 다이어그램에서 각 셀 Ri는 볼록 다각형이며, 원 Ci와 다른 각 원의 근축으로 경계 지어진 반공간들의 교차점이다. 세 셀의 꼭짓점은 다이어그램의 꼭짓점에서 만나는 세 원의 기저 중심이다.

 관련 구성 
파워 다이어그램은 점 위치 집합의 보로노이 다이어그램의 가중치 형태, 즉 평면을 특정 위치가 다른 모든 위치보다 가까운 셀로 분할하는 것으로 볼 수 있다. 가중 보로노이 다이어그램의 다른 형태로는 가산적으로 가중된 보로노이 다이어그램이 있는데, 이 다이어그램에서는 각 위치에 가중치가 부여되어 다른 위치까지의 거리와 비교하기 전에 거리에 더해진다. 또한 곱셈적으로 가중된 보로노이 다이어그램에서는 위치의 가중치가 다른 위치까지의 거리와 비교하기 전에 거리에 곱해진다. 이와 대조적으로, 파워 다이어그램에서는 각 원의 중심을 위치로 보고, 각 원의 제곱 반지름을 제곱 유클리드 거리에서 빼서 다른 제곱 거리와 비교하기 전에 빼는 가중치로 볼 수 있다. 모든 원 반지름이 같을 경우, 이 빼기는 비교에 영향을 미치지 않으며 파워 다이어그램은 보로노이 다이어그램과 일치한다.

평면 파워 다이어그램은 가중치가 없는 3차원 보로노이 다이어그램의 평면 단면으로도 해석될 수 있다. 이 해석에서 단면 평면의 원 중심 집합은 3차원 보로노이 위치의 수직 투영이며, 각 원의 제곱 반지름은 해당 위치와 단면 평면 사이의 제곱 거리에서 상수 K를 뺀 값인데, K는 이 모든 반지름을 양수로 만들기에 충분히 크게 선택된다..

보로노이 다이어그램과 마찬가지로, 파워 다이어그램은 모든 차원의 유클리드 공간으로 일반화될 수 있다. d차원의 n개 구의 파워 다이어그램은 d + 1차원의 n개 위를 향하는 반공간 집합의 교차점과 조합론적으로 동일하며 그 반대도 마찬가지다.

 알고리즘 및 응용 
2차원 파워 다이어그램은 O(n log n) 시간에 실행되는 알고리즘으로 구성될 수 있다. 더 일반적으로, 고차원 반공간 교차점과의 등가성 때문에 d차원 파워 다이어그램(d > 2인 경우)은  시간에 실행되는 알고리즘으로 구성될 수 있다.

파워 다이어그램은 구의 합집합 부피를 계산하는 효율적인 알고리즘의 일부로 사용될 수 있다. 각 구를 해당 파워 다이어그램 셀과 교차시키면 전체 합집합에 대한 기여도가 산출되며, 이를 통해 파워 다이어그램의 복잡도에 비례하는 시간 안에 부피를 계산할 수 있다..

파워 다이어그램의 다른 응용으로는 점이 디스크 합집합에 속하는지 테스트하는 자료 구조, 디스크 합집합의 경계를 구성하는 알고리즘, 및 구 집합에서 가장 가까운 두 개의 구를 찾는 알고리즘이 있다.. 또한 반이산 최적 수송 문제를 해결하는 데 사용되며, 이는 초기 우주 재구성 또는 유체 역학과 같은 다양한 응용 분야를 가진다.

 역사 
는 파워 거리의 정의가 19세기 수학자 에드몽 라게르와 게오르기 보로노이의 연구로 거슬러 올라간다고 추적한다. 는 파워 다이어그램을 정의하고 이를 사용하여 n개의 원형 디스크 합집합의 경계가 항상 최대 2n개의 점 광원에서 조명될 수 있음을 보여주었다.. 파워 다이어그램은 "라게르-보로노이 다이어그램", "디리클레 셀 복합체", "기저 보로노이 테셀레이션" 및 "단면 디리클레 테셀레이션"을 포함한 다른 이름으로 문헌에 등장했다..

 각주 

분류:다이어그램
분류:계산기하학