Algorithm for computing the circle set Voronoi diagram using edge-flip operations

• 영문명: Algorithm for computing the circle set Voronoi diagram using edge-flip operations
• 발행기관: 한국산업경영시스템학회
• 저자명: Deok-Soo Kim Donguk Kim Kwangseok Yu Junghun Lim Dong-Soo Cho Kokichi Sugihara
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2002년 추계국제학술대회, 321~326쪽, 전체 6쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2002.10.01

영문 초록

  Presented in this paper is an algorithm to compute the Voronoi diagram of a circle set from the Voronoi diagram of a point set. The circles are located in Euclidean plane, the radii of the circles are non-negative and not necessarily equal, and the circles are allowed to intersect each other. The idea of the algorithm is to use the topology of the point set Voronoi diagram as a seed so that the correct topology of the circle set Voronoi diagram can be obtained through a number of edge flipping operations. Then, the geometries of the Voronoi edges of the circle set Voronoi diagram are computed. The main advantages of the proposed algorithm are in its robustness, speed, and the simplicity in its concept as well as implementation.

목차

Abstract
1. Introduction
2. Preliminaries
3. Topology update
4. Geometry update
5. Implementation and examples
6. Conclusions
Acknowledgements
References