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.

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

• 조영송(한양대학교 보로노이다이어그램연구단)
• 김동욱(한양대학교 보로노이다이어그램연구단)
• 김덕수(한양대학교 산업공학과)