Topology-oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagram of Disks and Balls

Abstract

보로노이 다이어그램은 입자들 사이의 공간적 추론을 하는데 유용하며 그 계산을 위한 많은 연구가 발표되어 있지만 이전 연구의 대부분은 2 차원과 3 차원 점들의 보로노이 다이어그램에 대한 연구이다. 본 논문에서는 2 차원에서 원의 보로노이 다이어그램과 3 차원에서 구의 보로노이 다이어그램을 계산하는 강건한 알고리즘을 제시하고자 한다. 본 논문에서 제시하는 위상 기반 증가 (TOI) 알고리즘은 이미 계산된 중간 단계의 보로노이 다이어그램에 위상 정보에 우선 순위를 두어 새로운 원 또는 구를 추가하면서 보로노이 다이어그램을 계산한다. TOI 알고리즘은 평균적으로 O(n)의 시간 복잡도를 가지며, 최악의 경우 2 차원 원의 TOI 알고리즘은 O(n2), 3 차원 구의 TOI 알고리즘은 O(n3)의 시간 복잡도를 갖는다. TOI 알고리즘은 이미 구현되어 있고, 다른 알고리즘과의 비교를 통해 철저히 테스트되었다.; Voronoi diagrams are useful for spatial reasoning among particles and many studies were reported on their construction. However, most prior works were for the ordinary Voronoi diagram of points in the two- or three-dimensional space. In this thesis, we propose a robust algorithm for constructing the Voronoi diagram of circular disks and spherical balls in the two- and three-dimensional space, respectively. The proposed topology-oriented incremental (TOI) algorithm constructs the Voronoi diagram in O(n) on average and O(n^2) (for disks) and O(n^3) (for balls) by incrementing a generator to an already-constructed intermediate Voronoi diagram with a priority on the topology. The TOI-algorithm was implemented and thoroughly tested to benchmark against other algorithms.