We are given a set of N circles and M line segments in a 2-D space. Can any way be suggested to find which circles are intersected by each of the line segment with the minimum time complexity?
Asked
Active
Viewed 100 times
-1
-
1Missing details: order of magnitude of M and N ? are all circles and segments known upfront ? intersection with circles or disks ? how large are the circles and segments compared to their spacing ? (please show a sample) do you want a theoretically optimal or a practical algorithm ? – May 02 '17 at 08:52
-
Partial answer: you can build the Voronoi diagram of the set of line segments (`O(Ns Log Ns)` time for non-intersecting segments). Then for a given circle, the solution is given by the Voronoi cells that intersect it. The absence of intersection can be proven by finding the closest segment, which is obtained by point location in the Voronoi diagram, in time `O(Log Ns)`. – May 02 '17 at 09:11
1 Answers
0
If you have one line segment and one set of N circles, then complexity won't be better than linear O(N).
Just walk through circle list and check whether (squared) distance from circle center to segment is less than circle (squared) radius. Example od distance calculation
-
Should check if distance is <= radius -- the line could be tangent to the circle. – Matthew Burke May 01 '17 at 13:46
-
If there is a set of M line segments and for each we need to find the circles intersecting it? – Coder404 May 01 '17 at 13:57
-
@Coder404 This is another question :) Perhaps some space partition scheme exists for circles. – MBo May 01 '17 at 14:14