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)

Leptophyllous

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.

Issue

You assume that the required circle, always passes through p and q... Why should this be true?? – Externality

@Kshitij Banerjee It is true, because I always find a circle that satisfies the requirements and passes through p and q. The part starting "If you go far enough to the left" proofs why it is true. Briefly, if I start with my center far on the left, nothing is inside, as I go to the right, eventually everything gets inside, so sometimes in between exactly n are inside. – Issue

How does it work for this..? There may even be no other point on that axis.. :/ – Externality

@Kshitij Banerjee What I say is that there is a point c on the axis A (but not necessarily in S), such that the circle centered in c and passing through p and q is a solution. – Issue

Ah..i see. Still, My concern is that your solutions assumption is that taking any two points on the hull, the solution can 'always' be found with a third point in S. If that is so, then there will be multiple solutions to the problem. You can take the rightmost points as p and q and you can find the point s on the left. going left everything's inside.. going right nothing is.. If you can prove this assumption, i'd say the solution is perfect. But, I fail to see why that would be true. – Externality

atupal's solution proves this assumption :) See comments there. – Externality

There typically are multiple solutions. I reformulated the part of my solution that proves what you call "the assumption". If it did not answer what you had in mind, then please be more specific about what your concern is. (Or are you not believing me that if you go far enough to the left, nothing will be inside and if you go far to the right everything will?) – Issue

No I dont doubt that. Never mind. I got the proof i was looking for. :) – Externality

+1. It would be beneficial to elaborate a little more on the sorting criteria. Specifically, to every point r other than p or q you associate the radius of the circumscribed circle for the triangle pqr, which can be found using any of the formulae described here: en.wikipedia.org/wiki/Circumscribed_circle#Triangles – Wyattwyche

One more thing to consider though: handling of the cases when the circle that passes through p and q and containing n points inside intersects more than one additional point. For example, take a rectangle with an additional point in the interior. If you start with p and q being one of the rectangle's sides than the described algorithm will find the circumscribed circle for the rectangle, which doesn't answer the question correctly. The correct answer would be a circle circumscribing the point on the interior as well as 2 OPPOSITE corners of the rectangle. – Wyattwyche

@Wyattwyche I am finding the center of the circle, not the radius, and then sort these centers by x-coordinate. I will add edit to mention how to do this. The problem mentioned in the second post does not occur, since the statement says: No three points collinear and no four on a circle. – Issue

@Wyattwyche The radii of the circumscribed circles do not work: Consider a point r close to the middle of the segment pq. Then it gives a circle of large radius, but r enters the circle C(c;p,q) earlier than points giving smaller radius, because the center of the circle going through p,q,r is far on the left. So you probably really need to sort by the positions of the centers, as I do, or by the angles under which r sees the segment pq, as atupal does. – Issue

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

Metathesis

Interesting idea. However, there is one catch, if xy is a chord of the circle, then it subtends different angles on its circumference on its two different sides. (theta1 + theta2 = 180 degrees) – Centrosphere

That's clever +1 for the thought! It also proves the assumption I mentioned on pepan's solution!.. There are 2n+1 points remaining after choosing the two.. and the middle angle point will always clearly partition it in 2 sets of n :) – Externality

@Metathesis But how to calculate the step 1 i.e. 2 points on convex polygon with n points inside it in O(n) time? – Photocopier

@Metathesis I guess this will be a O(n^3) for getting 2 points and O(nlogn) for getting the middle angle algorithm. – Photocopier

@ArchitMaheshwari For example: a. Select the most left and bottom point x (O(n)) b. Select any a point y whose Polar Angle with x is biggest. (O(n)). Then we get 2 points x and y on convex polygon with n points inside it in O(n) time – Metathesis

@Metathesis But selecting a convex polygon with maximum angle will give 2n+1 points inside it. Please correct if i am missing something? – Photocopier

@ArchitMaheshwari What you means "give 2n+1 points inside it". In step 1 we only select two points so they can not construct a circle, We need find the 3rd point to construct a circle. – Metathesis

Ok Got it! Misunderstood the scenario. Very innovative solution. Thanks for the help! – Photocopier

Answer 3

You could consider using a QuadTree: Quadtree on wiki Then using this structure you could scan the proximity of each node. There seems to be a function called Query Range. This function will allow you to be more precise than just exhaustively picking circles I think.

Note this is not the solution, just an idea to get you started.

Orv

With naive alg he is enumarating sets of 3 point to build circles. So they are precise, not random. Maybe QuadRange can help a bit to check how much of points inside of the circle, but i can't see how can it help to avoid of O(n^3) - it is most important part. – Dissect

I replaced randomly with exhaustively – Orv

For every point you scan the proximity until it contains n points. Then draw a circle with the most distant points (will be a unique since no 4 lie on a circle). I would think this approach is O(n^2), where is the third power coming from, am i missing something? – Orv

Answer 4

At the ideal condition, when the circle has n points outside, n inside and 3 on it, The distance from the center of exactly n points will be more than the radius, and exactly n points less than the radius.. and only 3 points equal to the radius.. This will help you see how many are outside/inside quickly at a particular instant..

Make a vornoi diagram on the 2D points, this helps in finding which point is near to which other points.. Search on it if you need to know the concept.

Start by making a circle from any 3 adjacent points.. store the distance of all points to the center of this circle in an array.. points with distance more than R are outside and distance less are inside.

Progressively, leave a point on the circle and choose a point nearest to the boundary of the circle but outside the circle, to make a new circle.. and recalculate the array.

If we call the count of points inside as Nin and count of outside as Nout.. Nout will start decreasing and Nin will start increasing slowly. Keep doing this till they become equal( ur done, if so) or Nin exceeds Nout.. If this happens, make a new circle by choosing a point inside and near the boundary. Keep doing this until you get Nin == Nout at which point you have the solution..

Note that, taking the new point outside the circle, would increase the circle radius, and taking the new point inside the circle decreases the radius.

This is the first decent solution that came to my mind. This may need improving on certain aspects. I would expect the complexity to be much better than a brute force solution. I leave the calculation to you. :)

Externality

Answer 5

An easy way to solve this problem in O(n) time is to use inversion in a circle.

General Outline

Pick any point O(x,y) from the set to be the origin, and pick a circle of radius r with your chosen point as center. The calculations will be simplified if all points are translated by an amount (-x,-y) so that the point O becomes the origin.

Once you have chosen an origin and a circle, perform the operation of inversion with respect to your chosen circle to all the other points in the set. In coordinates, we map the point P(x,y) to the new point P' with coordinates (x',y') = (x,y)*r^2/(x^2+y^2). The origin O(0,0) goes to the point at infinity.

With the inversion transformation, the problem reduces to finding a line with the required properties (passes through two of the transformed points because a line always passes through the point at infinity; furthermore the line should split the remaining transformed points into two equal sets).

Note that inversion maps the set of 3 collinear and 4 concentric points onto the set of 3 collinear and 4 concentric points, so in the transformed set we have no 3 collinear points and no 4 concentric points.

To construct the circle, we then perform the inverse inversion (which is the same as the original inversion, since inversion in a circle is an involution, a self-inverse transformation). That pulls the line back to a circle passing through the first chosen point and two other points from the original set. Half the remaining points are inside the circle, half outside.

Corresponding Problem with Lines

Now we have reduced the problem to the following: given 2n+2 points in the plane, find a line passing through 2 of the points such that of the remaining 2n points, n are on one side of the line and n are on the other.

We can answer that question in O(n) time as follows. First, we need a single point in the boundary of the convex hull of the set (we don't need the whole convex hull). We can find such a point P by finding the point(s) in the set with coordinates minimum x value, which can be done in O(n) time using the Quickselect algorithm.

Now we know that all our points are in the half-space to the right of P. The idea of the next step is to find the point Q with median angle of all points with respect to the horizontal line h through P. Again, that can be accomplished in O(n) time using the Quickselect algorithm. There can be no two points with the same angle because there cannot be three points which are collinear.

The line PQ passes through two of the points and separates the remaining points R into two equal parts according to whether the angle RPh is greater than QPh or less than QPh (negative angles are below h).

One small problem can potentially arise: if the line passes through the origin, then inversion takes it to another line, not to a circle. However that situation cannot arise because it would mean that we had 3 collinear points in the original set, guaranteed not to be the case by the problem statement.

Hotshot

Answer 6

I am have no clue about time complexity, but this would be a mathematical algorithm that would work:

• Take any two points A, B such that all of the remaining points lie on the same side of AB.
• Order the points X_1,...,X_{2n} points such that angle AX_iB< angle AX_{i+1}B.

This is possible as no four points lie on a circle. Then the circle (AX_{n+1}B) contains exactly n points inside and n points outside.

Walling