This thesis proposes the algorithm that construct Voronoi diagram for the circle set, whose radii are dynamically changed. In this thesis, we consider the circle set with no constraints. That is, the circles may have negative radii, intersect each other, even contain one another.
While the site expands or shrinks from the point(the center of the circle) to the circle with the desired radius, the corresponding Voronoi region accordingly expands or shrinks. At some point of time the topological states changed, and we define this moment as an event. Whenever the events occur, we update the topological information and the geometric information. Finally we complete the Voronoi diagram for the circles with the desired radii. Two cases of the Region Expansion (When we increase the radius of the circle) and the Region Shrinkage (when we decrease the radius) have the two events, on-edge creating event and on-edge destroy event respectively.
본 논문에서는 평면 상의 원집합에 대한 보로노이 다이어그램을 구성하는 방법을 제안한다. 이 때 본 연구에서 대상으로 하는 원집합은 제약조건이 없다. 즉, 원의 반지름은 음의 값이 될 수도 있으며 임의의 실수값을 가지고, 원의 중심점의 좌표 역시 임의의 실수를 가진다고 가정하여, 원간의 교차나 표함 관계가 존재할 수 있다. 이 논문의 주요한 아이디어는 한 원의 반지름을 동적으로 확장하거나 축소시킴으로써 새로운 보로노이 다이어그램을 구성하는 것이다. 원이 확장되거나 축소될 때 해당 보로노이 영역 역시 원을 따라 확장되거나 축소되며, 그 과정에서 초기의 보로노이 다이어그램으로부터 위상정보가 변하는 순간이 발생한다. 이러한 순간을 이벤트로 정의하면, 원이 확장되거나 축소될 때 각각 해당 보로노이 영역의 edge가 증가하거나 감소하는 경우가 생긴다. 이 이벤트들을 계산하여 이에 따라 알맞게 위상정보와 기하정보만을 변화시킴으로써 보로노이 다이어그램을 새로 생성하지 않고 동적으로 보로노이 다이어그램을 재구성할 수 있다. 이러한 과정을 초기의 점집합의 보로노이 다이어그램을 구성하여 모든 circle이 목표 반지름에 도달할 때까지 진행함으로써 효율적으로 완성된 보로노이 다이어그램을 생성할 수 있다.
