영역 확장법을 통한 평면에서 원들의 보로노이 다이어그램의 강건한 계산

• 영문명: Robust Construction of Voronoi Diagram of Circles by Region-Expansion Algorithm
• 발행기관: 한국산업경영시스템학회
• 저자명: 김동욱(Donguk Kim)
• 간행물 정보: 『산업경영시스템학회지』제42권 제3호, 52~60쪽, 전체 9쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2019.09.30

영문 초록

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 he 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. 배경 이론

3. 영역 확장법

4. 구현 및 실험

5. 결 론

키워드

Voronoi Diagram of Circles Robust Algorithm Quasi-Triangulation Additively Weighted Voronoi Diagram