What is an algorithm for enclosing the maximum number of points in a 2-D plane with a fixed-radius circ… by @chhung6
Answer by Chun-Ho Hung:
There is an [math]O(N^2 \log N)[/math] deterministic algorithm. This is usually (if not always) sufficient for competitive programming contests / online judges (e.g., POJ 1981 Circle and Points).
Idea:
If there exists a circle C that encloses M points, then by slightly moving C it will touch at least two points. [1]
So, essentially we just need to check all circles which touch (at least) 2 points:
- For each pair of points in the given set, construct a circle with radius R that touches both points. For each point pair there are at most two such circles.
- For each constructed circle, check for each of the given points is inside it.
- Return the circle that encloses the maximum number of points.
The runtime of this algorithm is [math]O(N^3)[/math] because there are at most [math]O(N^2)[/math] such circles in step 1, and the linear scan at step 2 takes [math]O(N)[/math] time.
Runtime Improvement:
So, how can we achieve [math]O(N^2 \log N)[/math]?
The idea is as follows:
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 [math]\theta[/math], where [math](r, \theta)[/math] 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 [math]\theta[/math].
(Figure from Wikipedia: Points in a polar coordinate system)
For each other point Q (≠ P), we can actually compute the range of [math]\theta[/math] for which C covers Q. Put more formally, C encloses Q whenever (iff) [math]\theta \in [\alpha, \beta][/math]. [2]
So, up to this point, the original problem has been reduced to:
What is an optimal value of [math]\theta[/math] that lies in the most number of [math][\alpha, \beta][/math] intervals?
The reduced problem can be solved with a pretty standard [math]O(N \log N)[/math] algorithm.[3] This reduced problem has to be solved N times (one for each point P), hence the time complexity [math]O(N^2 \log N)[/math].
Remarks:
The above algorithms assume that a point is considered being enclosed in a circle even if it is on the circumference. If not, we could still tweak them a bit, for example, by changing the intervals of [math]\theta[/math] from being close-close to close-open. (Hmm, probably – didn't think too much to verify, but you get the idea.)
[1]: Unless all pairwise distances are > 2R, where the answer to the maximum number of points will be 1. This can be checked in [math]O(N^2)[/math] time.
[2]: We ignore Q's with distance > 2R from P.
[3]: Probably need to be careful when handling these cyclic intervals.