CODEWITHSUNDEEP
algorithmmathgeometry
Rahul K Singh
Rahul K Singh

Reputation: 189

Implementation of Radial Sweep

You have given N points in 2D plane ,i need to find out the smallest radius of a circle that contain at least M points .

Approach I am using :-

I will do binary search on radius of circle .

Pick an arbitrary point P from the given set. We rotate a circle C with radius R using P as the "axis of rotation" (by convention, in the counter-clockwise direction), i.e. we keep C to touch P any time during the rotation. While C is being rotated, we maintain a counter to count the number of points C encloses.

Note that this counter only changes when some point Q enters (or leaves) the region of the circle C. Our goal is to come up with an algorithm that will increment (or decrement) this counter, whenever some other point Q ≠ P enters (or leaves) the region of C.

The state of the (rotating) circle C can be described by a single parameter θθ, where (r,θ) are the polar coordinates of the center of the circle C, if we pick P as the fixed point of the polar coordinate system. With this system, rotating C means increasing θ.

For each other point Q (≠ P), we can actually compute the range of θ for which C covers Q. Put more formally, C encloses Q whenever (iff) θ∈[α,β].

So, up to this point, the original problem has been reduced to:

What is an optimal value of θ that lies in the most number of [α,β] intervals?

The reduced problem can be solved with a pretty standard O(NlogN) algorithm.[3] This reduced problem has to be solved N times (one for each point P), hence the time complexity O(N2logN).

I am able to get the how to do this step :

For each other point Q (≠ P), we can actually compute the range of θ for which C covers Q. Put more formally, C encloses Q whenever (iff) θ∈[α,β]. So, up to this point, the original problem has been reduced to: What is an optimal value of θ that lies in the most number of [α,β]intervals?

can you please suggest how to implement that part .

Upvotes: 1

Views: 1203

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

When Q enters or leaves the circle C (with radius R):

  • The distance between P and C's center is R (because it always is); and

  • The distance between Q and C's center is also R

So, if you draw a circle of radius R around Q, and a circle of radius R around P. The two points at which they intersect are the centers of C when Q enters or leaves.

Let ±θ be the angles between those centers of C and line PQ. If you draw it out you can easily see that |PQ|/2R = cos(θ), which makes it pretty easy to find the angles you're looking for.

Upvotes: 2

Related Questions