Intersection and Closest-Pair Problems for a Set of Planar Discs
Micha Sharir · SIAM Journal on Computing · 1985
Efficient algorithms for detecting intersections and computing closest neighbors in a set of circular discs, are presented and analyzed. They adapt known techniques for solving these problems for sets of points or of line segments. The main portion of the paper contains the construction of a generalized Voronoi diagram for a set of n (possibly intersecting) circular discs in time $O(n\log ^2 n)$, and its applications.