본문으로 이동

파워 다이어그램

위키백과, 우리 모두의 백과사전.
네 원의 파워 다이어그램

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

정의

[편집]
주어진 원 밖에 있는 점 P의 방멱

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

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

두 교차하는 원의 근축. 두 원의 파워 다이어그램은 이 선으로 형성된 두 반평면으로 평면을 분할한 것이다.

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

관련 구성

[편집]

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

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

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

알고리즘 및 응용

[편집]

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

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

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

역사

[편집]

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

각주

[편집]
  1. ↑ Linhart, J. (1981), “Dirichletsche Zellenkomplexe mit maximaler Eckenzahl”, 《Geometriae Dedicata》 11 (3): 363–367, doi:10.1007/BF00149360, MR 627538, S2CID 120072781 .
  2. ↑ 가 나 다 라 마 바 사 Imai, Hiroshi; Iri, Masao; Murota, Kazuo (1985), “Voronoĭ diagram in the Laguerre geometry and its applications”, 《SIAM Journal on Computing》 14 (1): 93–105, doi:10.1137/0214006, MR 774929 .
  3. ↑ 가 나 다 라 마 바 사 아 자 Aurenhammer, F. (1987), “Power diagrams: properties, algorithms and applications”, 《SIAM Journal on Computing》 16 (1): 78–96, doi:10.1137/0216006, MR 873251 .
  4. ↑ 가 나 다 라 마 Edelsbrunner, Herbert (1987), 〈13.6 Power Diagrams〉, 《Algorithms in Combinatorial Geometry》, EATCS Monographs on Theoretical Computer Science 10, Springer-Verlag, 327–328쪽 .
  5. ↑ Ash, Peter F.; Bolker, Ethan D. (1986), “Generalized Dirichlet tessellations”, 《Geometriae Dedicata》 20 (2): 209–243, doi:10.1007/BF00164401, MR 833848, S2CID 120383767 .
  6. ↑ Avis, David; Bhattacharya, Binay K.; Imai, Hiroshi (1988), “Computing the volume of the union of spheres” (PDF), 《The Visual Computer》 3 (6): 323–328, doi:10.1007/BF01901190 .
  7. ↑ Guibas, Leonidas; Zhang, Li (1998), 〈Euclidean proximity and power diagrams〉, 《10th Canadian Conference on Computational Geometry》 .
  8. ↑ Aurenhammer, F.; Hoffmann, F.; Aronov, B. (January 1998). 《Minkowski-Type Theorems and Least-Squares Clustering》 (영어). 《Algorithmica》 20. 61–76쪽. doi:10.1007/PL00009187. ISSN 0178-4617. S2CID 5409198. 
  9. ↑ Levy, Bruno; Mohayaee, Roya; von Hausegger, Sebastian (2021년 7월 13일). 《A fast semidiscrete optimal transport algorithm for a unique reconstruction of the early Universe》 (영어). 《Monthly Notices of the Royal Astronomical Society》 506. 1165–1185쪽. arXiv:2012.09074. doi:10.1093/mnras/stab1676. ISSN 0035-8711. 
  10. ↑ Lévy, Bruno (February 2022). 《Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries》 (영어). 《Journal of Computational Physics》 451. 110838쪽. arXiv:2106.03936. Bibcode:2022JCoPh.45110838L. doi:10.1016/j.jcp.2021.110838. S2CID 235406800. 
  11. ↑ Fejes Tóth, L. (1977), “Illumination of convex discs”, 《Acta Mathematica Academiae Scientiarum Hungaricae》 29 (3–4): 355–360, doi:10.1007/BF01895856, MR 0464065, S2CID 122510545 .
  12. ↑ Aurenhammer, F.; Imai, H. (1988), “Geometric relations among Voronoĭ diagrams”, 《Geometriae Dedicata》 27 (1): 65–75, doi:10.1007/BF00181613, MR 950323 .
원본 주소 "https://ko.wikipedia.org/w/index.php?title=파워_다이어그램&oldid=40532587"