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(nlog ² n), and its applications.
No takes yet. Share an insight, caveat, or question.
Micha Sharir (1985) studied this question.