Algorithm for Finding a circle among 2n+3 points such that it contains n points inside, n points outside and 3 points on itself

Question

Following is a question from careercup.com's Google Interview section:

Given 2*n + 3 points in 2d space, with no 3 points collinear and no 4 points lying on a circle,
devise an algorithm that will find a circle that contains n points inside it, n outside it and 3 on it.

I can think of a O(n^4) solution:
a) Pick any 3 points [in C(2n+3,3) ways] and make a circle with these (O(n^3))
b) Now for each circle, check if exactly 'n' points lie inside it O(n)

Since this is a naive approach, I would like to ask if there is a better way
to approach this problem? i.e. something in the order of O(n log n)

Answer 1

Here is an O(n) solution.

Let S be the set of points. Let p be the leftmost point of S. Then p is on the convex hull of S. Let q be the point of S minimizing the angle between the ray going to the left from p and the ray starting at p and going through q. Both p and q can be found in O(n) time. The segment pq is an edge of the convex hull of S and no point of S lies to the left of the line pq.

Take the axis A of the segment pq. The centers of circles containing p and q are exactly the points on the axis A. For every point c on A, let C(c;p,q) be the circle centered at c and containing p and q. If c is a point of A far enough to the left, then C(c;p,q) has no point of S inside. If c is a point of A far enough to the right, then C(c;p,q) has all points of S other than p,q inside (p and q are on the circle). If we move c from the left to the right, points of S are entering the circle C(c;p,q) one by one and never leaving. So somewhere in between, there is a point c on A such that C(c;p,q) contains p,q and one more point of S and has exactly n other points of S inside.

This can be clearly found in O(n logn): For every point s of S other than p and q, find the point c on A such that C(c;p,q) contains p,q and s. The point c is the intersection of the axis A and the axis of the segment qs. Notice that when we were passing through c while we were moving along A, s entered the circle C(c;p,q). Sort these centers by increasing x-coordinates and take the (n+1)-st as this is the point when exactly n points of S are already inside C(c;p,q) and p, q and one more point are on C(c;p,q). To do it in O(n), you find the (n+1)-st without sorting them all.

Answer 2

Another O(n) algorithm, but more simple.

1. select any two points x, y on the convex polygon which encircles the n points set.
2. calculate the every remain point's angle with the x, y
3. select the point which's angle is middle.(Because we only need find the middle angle ,So the complex is O(n))

And this three point is the answer.

such as：

And because angle C < angle A , so point C outside the circle(made by A and x, y).
angle B > angle A, so point B inside the circle