CODEWITHSUNDEEP
algorithmcomputational-geometry
Tanu Saxena
Tanu Saxena

Reputation: 779

Segment Intersection

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.

Upvotes: 3

Views: 1179

Answers (4)

Shashank Rana
Shashank Rana

Reputation: 1

No your algorithm will not work. This is because unlike in case of line intersection, it is possible that the circle/disc intersecting the disc in hand is not consecutive. Let me give you an example.. Assuming you are making line segments out of circles by joining their left-most and right most points, and then using the CLRS algo to find if any lines intersect. You will find that at p3, the c3 is never consecutive to c1, but it intersects with c1.

The diagram

Upvotes: 0

salva
salva

Reputation: 10242

Another approach to solve the problem:

  1. Divide the plane using a grid whose diameter is that of the biggest circle.
  2. Use a hashing algorithm to classify the grid cells in N groups.
  3. For every circle calculate the grid cells it overlaps and the corresponding groups.
  4. Get all the circles in a group and...
    1. Check if the biggest circle touches any other circle in the group.
    2. Recurse applying this algorithm to the remaining circles in the group.

This same algorithm implemented in scala: https://github.com/salva/simplering/blob/master/touching/src/main/scala/org/vesbot/simplering/touching/Circle.scala

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

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.

Upvotes: 1

salva
salva

Reputation: 10242

  1. Build a k-d tree with the centres of the circles.
  2. For every circle (p, r), find using the k-d tree the set S of circles whose centres are nearer than 2r from p.
  3. Check if any of the circles in S touches the current circle.

I think the average cost for this algorithm is O(NlogN).

The logic is that we loop over the set O(N), and for every element get a subset of elements near O(NlogN), so, a priori, the complexity is O(N^2 logN). But we also have to consider that the probability of two random circles being less than 2r apart and not touching is lesser than 3/4 (if they touch we can short-circuit the algorithm).

That means that the average size of S is probabilistically limited to be a small value.

Upvotes: 0

Related Questions