원집합의 보로노이 다이어그램에 대한 동적 구현

Abstract

본 논문에서는 평면 상의 원집합에 대한 보로노이 다이어그램을 구성하는 방법을 제안한다. 이 때 본 연구에서 대상으로 하는 원집합은 제약조건이 없다. 즉, 원의 반지름은 음의 값이 될 수도 있으며 임의의 실수값을 가지고, 원의 중심점의 좌표 역시 임의의 실수를 가진다고 가정하여, 원간의 교차나 표함 관계가 존재할 수 있다. 이 논문의 주요한 아이디어는 한 원의 반지름을 동적으로 확장하거나 축소시킴으로써 새로운 보로노이 다이어그램을 구성하는 것이다. 원이 확장되거나 축소될 때 해당 보로노이 영역 역시 원을 따라 확장되거나 축소되며, 그 과정에서 초기의 보로노이 다이어그램으로부터 위상정보가 변하는 순간이 발생한다. 이러한 순간을 이벤트로 정의하면, 원이 확장되거나 축소될 때 각각 해당 보로노이 영역의 edge가 증가하거나 감소하는 경우가 생긴다. 이 이벤트들을 계산하여 이에 따라 알맞게 위상정보와 기하정보만을 변화시킴으로써 보로노이 다이어그램을 새로 생성하지 않고 동적으로 보로노이 다이어그램을 재구성할 수 있다. 이러한 과정을 초기의 점집합의 보로노이 다이어그램을 구성하여 모든 circle이 목표 반지름에 도달할 때 까지 진행함으로써 효율적으로 완성된 보로노이 다이어그램을 생성할 수 있다.