Segment Intersection

Question

Here is a question from CLRS. A disk consists of a circle plus its interior and is represented by its center point and radius. Two disks intersect if they have any point in common. Give an O(n lg n)-time algorithm to determine whether any two disks in a set of n intersect.

Its not my home work. I think we can take the horizontal diameter of every circle to be the representing line segment. If two orders come consecutive, then we check the length of the distances between the two centers. If its less than or equal to the sum of the radii of the circles, then they intersect.

Please let me know if m correct.

Answer 1

Build a Voronoi diagram for disk centers. This is an O(n log n) job.

Now for each edge of the diagram take the corresponding pair of centers and check whether their disk intersect.