Region-Expansion for the Construction of the Construction of the Voronoi Diagram for Spheres in 3D

• 영문명: Region-Expansion for the Construction of the Construction of the Voronoi Diagram for Spheres in 3D
• 발행기관: 한국산업경영시스템학회
• 저자명: 김동욱 조영송 김덕수
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2005년 춘계학술대회 논문집, 45~50쪽, 전체 6쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2005.05.01

영문 초록

  It is known that Voronoi diagrams have many important applications in science and engineering as a useful tool for analyzing spatial properties among geometric objects. In this paper, we propose an algorithm to construct Euclidean Voronoi diagram for spheres in 3-dimensional space. Starting from the ordinary Voronoi diagram of centers of spheres, the proposed region-expansion algorithm constructs the desired diagram by expanding Voronoi regions for one sphere after another via a series of topology operations. While the worst-case time complexity is O(n³ log n) for the whole diagram, its expected time complexity can be much smaller.

목차

Abstract
1. Introduction
2. Definition and Properties of the Euclidean Voronoi diagram for spheres
3. Region-Expansion Algorithm
4. Algorithm
5. Implementation example
6. Conclusions
Acknowledgement
References

키워드

Voronoi diagram Region-Expansion Algorithm