Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Robust and Fast Algorithm for a Circle Set Voronoi Diagram in a Plane
| |
|
Robust and Fast Algorithm for a Circle Set Voronoi Diagram in a Plane
Deok-Soo Kim5 , Donguk Kim5 , Kokichi Sugihara6 and Joonghyun Ryu5 
| (5) |
Department of Industrial Engineering, Hanyang University, 17 Haengdang-Dong, Sungdong-Ku, Seoul, 133-791, Korea |
| (6) |
Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Tokyo, 7-3-1, Hongo, Bunkyo-ku, Tokyo 113, Japan |
Abstract
Robust and fast computation of the exact Voronoi diagram of circle set is difficult. Presented in this paper is an edge-flipping
algorithm that computes a circle set Voronoi diagram using a point set Voronoi diagram, where the points are the centers of
circles. Hence, the algorithm is as robust as its counterpart of point set. Even though the theoretical worst-case time complexity
is quadratic, the actual performance shows a strong linear time behavior for various test cases. Furthermore, the computation
time is comparable to the algorithm of point set Voronoi diagram itself.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|