The algorithm for finding a circle of 2n + 3 points, so that it contains n points inside, n points outside and 3 points on itself

Question

The following is a question from the Google Careercup.com interview section:

Given 2 * n + 3 points in a 2d-space, without three points, collinear and without 4 points lying on a circle,
come up with an algorithm that finds a circle containing n points inside it, n outside it and 3 on it.

I can think of a solution O (n ^ 4):
a) Choose any 3 points [in C (2n + 3,3) paths] and make a circle with these (O (n ^ 3))
b) Now for each circle we check whether there are exactly "n" points of O (n) in it

Since this is a naive approach, I would like to ask if there is a better way to approach this problem? that is, something is ok O (n log n)

Answer 1

Here is a solution to O (n).

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 S minimizing the angle between the ray going to the left of p and the ray starting from p and passing 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 not a single 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 precisely points on the axis A. For each point c on A, let C (c; p, q) be a circle centered in c containing p and q. If c is a point A far enough to the left, then C (c; p, q) does not have a point S inside. If c is a point A far enough to the right, then C (c, p, q) has all points from S different from p, q inside (p and q are on a circle). If we move c from left to right, points S enter the circle C (c; p, q) one after another and never leave. So, somewhere in the middle there is a point c on A such that C (c; p, q) contains p, q and another point S and has exactly n other points from S inside.

This can be found in O (n logn): for every point s in S other than p and q, find a point c on A such that C (c; p, q) contains p, q and s. Point c is the intersection of the axis A and the axis of the segment qs. Note that when we passed through c, when we moved along A, s entered the circle C (c; p, q). Sort these centers by increasing the x-coordinates and take (n + 1) -st, since this is a point when exactly n points from S are already inside C (c; p, q) and p, q and another point on C (s; p, d). To do this in O (n), you will find (n + 1) -st without sorting them all .

Answer 2

Another algorithm is O (n), but simpler.

• select any two points x, y on a convex polygon that surrounds n points of the set.
• calculate each remaining point angle using x, y
• Select a point whose angle is average. (Because we only need the average angle, so the complex is O (n))

And these are three questions - this is the answer.

eg:

And since the angle C <angle A, therefore, the point C is outside the circle (A and x, y are made).
angle B> angle A, therefore point B inside the circle

Answer 3

You can use QuadTree : Quadtree on the wiki. Then, using this structure, you can scan the proximity of each node. It seems that the function is called Query Range . This feature will allow you to be more accurate than just the exhaustive circles that I think.

Please note that this is not a solution, just an idea to get you started.

Answer 4

Ideally, when a circle has n points outside, n inside and 3 on it, the distance from the center of exactly n points will be greater than the radius, and exactly n points less than the radius .. and only 3 points are equal to the radius. This will help you see how many of them are outside / inside quickly at a particular moment.

Make a vornoi diagram on two-dimensional points, this helps to find which point is next to other points. Find it if you need to know the concept.

Start by creating a circle from any three adjacent points. save the distance of all points to the center of this circle in the array. Points with a distance are larger than R on the outside, and the distance is less on the inside.

Gradually leave a point on the circle and select the point closest to the border of the circle but outside the circle to create a new circle .. and recount the array.

If we call the number of points inside, like Nin, and the number of external points, Nout .. Nout will begin to decrease, and Nin will begin to slowly increase. Keep doing this until they become equal (ur did, if so) or Nin exceeds Nout .. If that happens, create a new circle by choosing a point inside and next to the border. Keep doing this until you get Nin == Nout, after which you will have a solution.

Note that taking a new point outside the circle will increase the radius of the circle, and a new point inside the circle will decrease the radius.

This is the first worthy decision that occurred to me. Perhaps this will require improvement in certain aspects. I would expect complexity to be much better than brute force solution. I leave you a calculation. :)

Answer 5

A simple way to solve this problem in O (n) is to use inverse in a circle .

General scheme

Select any point O (x, y) from the set to the origin and select a circle of radius r with the point you select in the center. The calculations will be simplified if all points are transferred to the sum (-x, -y), so that point O becomes the beginning.

Once you have selected the source and the circle, perform the inverse operation relative to the selected circle to all other points in the set. In the coordinates, we compare the point P (x, y) with the new point P 'with the coordinates (x',y') = (x,y)*r^2/(x^2+y^2) . The origin of O (0,0) goes to an infinite point.

With the inversion transformation, the task is to find a line with the required properties (it passes through two of the converted points, because the line always passes through an infinitely remote point, in addition, the line should divide the remaining converted points into two equal sets).

Note that the inversion maps a set of 3 collinear and 4 concentric points to a set of 3 collinear and 4 concentric points, so there are no 3 collinear points and not 4 concentric points in the converted set.

To construct a circle, we then perform a reverse inversion (which coincides with the original inversion, since the inversion in the circle is an involution, a self-inverse transformation). This draws the line back to the circle passing through the first selected point and two other points from the original set. Half of the remaining points are inside the circle, half outside.

Corresponding task with lines

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

We can answer this question O (n) times as follows. First, we need one point on the boundary of the convex hull of the set (we do not need the entire convex hull). We can find such a point P by finding point (s) in a set with a minimum value of x coordinates, which can be done O (n) times 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 the median angle of all points relative to the horizontal line h through P. Again, this can be done in O (n) times using the Quickselect algorithm. There cannot be two points with the same angle, because there cannot be three points that are collinear.

The line PQ passes through two points and divides the remaining points R into two equal parts, depending on whether the angle RPh is greater than QPh or less than QPh (negative angles below h).

One small problem arises: if the line passes through the origin, then the inversion transfers it to another line, and not to the circle. However, this situation cannot arise due to the fact that it would mean that we had 3 collinear points in the initial set, which would not be guaranteed as a result of the statement of the problem.