논문 상세보기

Robust Construction of Voronoi Diagram of Circles by Region-Expansion Algorithm KCI 등재

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

  • 언어KOR
  • URLhttps://db.koreascholar.com/Article/Detail/380967
구독 기관 인증 시 무료 이용이 가능합니다. 4,000원
한국산업경영시스템학회지 (Journal of Society of Korea Industrial and Systems Engineering)
한국산업경영시스템학회 (Society of Korea Industrial and Systems Engineering)
초록

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