โ Scribed by Li Jin; Donguk Kim; Lisen Mu; Deok-Soo Kim; Shi-Min Hu
No coin nor oath required. For personal study only.
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((nCm)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 2 ), the presented algorithm is optimal with O(n 2 log n) worst-case time complexity.
๐ SIMILAR VOLUMES
In this and the following papers, we present an algorithm to compute the exact Voronoi diagram of a circle set from the Voronoi diagram of a point set. The circles are located in a two dimensional Euclidean space, the radii of the circles are non-negative and not necessarily equal, and the circles a
We present a parallel algorithm for the Voronoi diagram of the set of vertices of a convex polygon. The algorithm runs in time O(logn) and uses O(n loglogn/log n) processors in the CRCW PRAM model. The concurrent write is used only by an integer sorting subroutine. We also obtain an O(log n)-time an