An Edge-Flip Algorithm for Computing a Voronoi Diagram of Circles in a Circle

• 영문명: An Edge-Flip Algorithm for Computing a Voronoi Diagram of Circles in a Circle
• 발행기관: 한국산업경영시스템학회
• 저자명: 김동욱 유광석 김덕수 Kokichi Sugihara
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2003년 추계학술대회 논문집, 112~115쪽, 전체 4쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2003.10.01

영문 초록

  Presented in this paper is an algorithm to compute a Voronoi diagram of circles in a circle, where circles are located in a large circle. Given circles in a large circle, the region in the plane is divided into regions associated with the given circles. The proposed algorithm uses point Voronoi diagram, and then some topological remedies are applied so that we obtain proper initial topology including enclosing circle. From this initial topology, we can obtain the correct topology by a series of edge-flip operations. After getting the correct topology, the equations of edges are computed and represented in a rational quadratic B？zier curve form.

목차

Abstract
1. Introduction
2. Basic procedure
3. Topology construction
4. Geometry construction
5. Examples
6. Conclusions
References

키워드

Voronoi diagrams edge-flip algorithm B？zier curves