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.
My Menu
Saved Items

Robust and Fast Algorithm for a Circle Set Voronoi Diagram in a Plane

Deok-Soo KimContact Information, Donguk KimContact Information, Kokichi SugiharaContact Information and Joonghyun RyuContact Information

(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.

Contact Information Deok-Soo Kim
Email: dskim@email.hanyang.ac.kr

Contact Information Donguk Kim
Email: donguk@cadcam.hanyang.ac.kr

Contact Information Kokichi Sugihara
Email: sugihara@simplex.t.u-tokyo.ac.jp

Contact Information Joonghyun Ryu
Email: jhryu@cadcam.hanyang.ac.kr
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)