논문 상세보기
3차원에서 구의 보로노이 다이어그램의 구성을 위한 영역 확장법
Region-Expansion for the Construction of the Voronoi Diagram for Spheres in 3D
조영송, 김동욱, 김덕수
- 언어ENG
- URLhttps://db.koreascholar.com/Article/Detail/354116
4,000원
초록
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(n3 log n) for the whole diagram, its expected time complexity can be much smaller.
키워드
Voronoi diagramRegion-Expansion Algorithm
목차
Abstract
1. Introduction
2. Definition and Properties of the Euclidean Voronoi diagram for spheres
3. Region-Expansion Algorithm
3.1 Region expansion process
3.2 Event types and handling
4. Algorithm
5. Implementation example
6. Conclusions
References
1. Introduction
2. Definition and Properties of the Euclidean Voronoi diagram for spheres
3. Region-Expansion Algorithm
3.1 Region expansion process
3.2 Event types and handling
4. Algorithm
5. Implementation example
6. Conclusions
References
저자
