This paper presents a numerically robust algorithm to construct a Voronoi diagram of circles in the plane. The circles are allowed to have intersections among them, but one circle cannot fully contain another circle. The Voronoi diagram is a tessellation of the plane into Voronoi regions of given circles. Each circle has its Voronoi region which is defined by a set of points in the plane closer to the circle than any other circles. The distance from a point p to a circle ci of center pi and radius ri is ||p-pi||-ri, which is the closest Euclidean distance from p to the circle boundary. The proposed algorithm first constructs the point Voronoi diagram of centers of given circles, then it enlarges each point to the circle and expands its Voronoi region accordingly. This region-expansion process is done by local modifications and after completing this process for the whole circles the desired circle Voronoi diagram can be obtained. The proposed algorithm is numerically robust and we provide with a few examples to show its robustness. The algorithm runs in O(n2) time in the worst case and O(n) time on average where n is the number of the circles. The experiment shows that the region-expansion algorithm is robust and runs fast with strong linear time behavior.

1. 서 론
2. 배경 이론
    2.1 점 집합 보로노이 다이어그램
    2.2 원 집합 보로노이 다이어그램
3. 영역 확장법
    3.1 영역 확장 과정
    3.2 이벤트의 발생
    3.3 컨벡스헐 주변에서의 이벤트
    3.4 영역 확장 알고리듬
    3.5 영역 확장 알고리듬의 수치적 안정성
4. 구현 및 실험
5. 결 론
References

• Donguk Kim(Department of Industrial and Management Engineering, Gangneung-Wonju National University) | 김동욱 Corresponding Author