A Sweepline Algorithm for Euclidean Voronoi Diagram of Circles

Li Jin Tsinghua University Donguk Kim Hanyang University Lisen Mu Tsinghua University Deok-Soo Kim Hanyang University Shi-Min Hu Tsinghua University

Computational Geometry mathscidoc:1608.09014

Computer-Aided Design, 38, (3), 260-278, 2006
Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others. The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed. The worst-case time complexity of the proposed algorithm is $O((n+m)log n)$, where $n$ is the number of input circles, and $m$ is the number of intersection points among circles. As $m$ can be $O(n^22)$, the presented algorithm is optimal with $O(n^2 log n) $ worst-case time complexity.
Sweepline Algorithm, Voronoi Diagram, Circles
[ Download ] [ 2016-08-24 23:32:33 uploaded by shimin ] [ 639 downloads ] [ 0 comments ] [ Cited by 22 ]
@inproceedings{li2006a,
  title={A Sweepline Algorithm for Euclidean Voronoi Diagram of Circles},
  author={Li Jin, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160824233233272057437},
  booktitle={Computer-Aided Design},
  volume={38},
  number={3},
  pages={260-278},
  year={2006},
}
Li Jin, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. A Sweepline Algorithm for Euclidean Voronoi Diagram of Circles. 2006. Vol. 38. In Computer-Aided Design. pp.260-278. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160824233233272057437.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved