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

Cthat enclosesMpoints, then byslightly movingCit 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
Rthat 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

Pfrom the given set. Werotate a circleCwith radiusRusingPas the "axis of rotation" (by convention, in the counter-clockwise direction), i.e. we keepCto touchPany time during the rotation. WhileCis being rotated, wemaintain a counterto count the number of pointsCencloses.Note that this counter

only changeswhen some pointQenters (or leaves) the region of the circleC. Our goal is to come up with an algorithm that will increment (or decrement) this counter, whenever some other pointQ≠Penters (or leaves) the region ofC.The state of the (rotating) circle

Ccan be described by asingle parameter [math]\theta[/math], where [math](r, \theta)[/math] are the polar coordinates of the center of the circleC, if we pickPas the fixed point of the polar coordinate system. With this system, rotatingCmeans increasing [math]\theta[/math].(Figure from Wikipedia: Points in a polar coordinate system)

For each other point

Q(≠P), we can actuallycompute the range of [math]\theta[/math]for whichCcoversQ.Put more formally,CenclosesQwhenever (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

Ntimes (one for each pointP), hence the time complexity [math]O(N^2 \log N)[/math].

## Remarks:

The above algorithms assume that a point is considered being

enclosedin a circle even if it ison 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 ignoreQ's with distance > 2RfromP.

[3]: Probably need to be careful when handling these cyclic intervals.