본문 바로가기
카테고리 없음

Voronoi diagram(보로노이 다이어그램)

by 비즈봉 2019. 4. 4.

< 용어 >

보로노이 다이어그램은 평면의 특정 집합의 점까지의 거리에 기초한 평면 영역의 분할을 뜻한다. Voronoi diagram(보로노이 다이어그램)은 Voronoi tessellation(보로노이 테셀레이션), Voronoi decomposition, Voronoi partition라고도 불리는 영역 분할 다이어그램이다. 1868년 우크라이나에서 태어난 러시아 수학자 조지 보로노이의 이름을 따서 지어졌다. 평면에서 뿐 아니라 3차원에서도 적용될 수 있다. 

< 활용 사례 >

공학, 생물학 (원자의 중심에 점을 찍고 3차원 보로노이 다이어그램을 그려서 식물세포의 분자 구조를 구하기도 함), 지리학 (공공시설의 관할구역 지정 시 택시기하를 이용한 보로노이 다이어그램이 이용), 건축디자인 (실제 베이징 올림픽 때 수영경기를 한 워터큐브에 적용) 과 예술에 걸쳐 여러 분야에 사용된다. 자연에서는 잠자리 날개, 원자가 결정구조로의 배열에도 보로노이 다이어그램이 나타난다.

데이터 클러스터링에도 사용되는데 주어진 데이터 분포에서 유의미한 클러스터를 뽑아내는 것

< 간단한 설명 >

사각형 공간에 점을 여러 개 찍어놓는다고 하자. (*점은 seeds, sites, generators라고도 불림)

그 각자의 점들이 가지는 영역이 있다고 생각하면 전체 영역의 분배가 편파적이지 않도록 전체 영역을 직선들로 나누어 주는 것이다.

일련의 점들은 각각 대응하는 구간이 다른 점보다 그 점에 가까운 두

보르노이 영역은 겉보기에 다각형들의 모임으로 보이는데 영역을 분할함에 있어 수학적인 원리가 들어있다.보로노이 다이어그램(Voronoi diagram)은 평면을 특정 점까지의 거리가 가장 가까운 점의 집합으로 분할한 그림이다. 들로네 삼각분할과 쌍대관계이다.

< 수학적 원리 >

보로노이 다이어그램의 작도법은 

1) 평면 위에 여러 개의 점을 찍는다. 

2) 가장 인접한 두 개의 점을 선택해 수직이등분선을 그린다.

3) 모든 점에 똑같이 적용한다.

https://blog.naver.com/weizmann_why/60171012330

댓글