Ruudddiiii's blog

Computational Geometry [ Finding the Circle ]
By Ruudddiiii, history, 9 months ago, In English

I have this problem where I have random points on a 2-D plane and i have to find the circle which is closest to all the Points. I have brute force solution of it which goes like this : 1) Select two sets of two points. 2) Calculate the perpendicular bisector for each pair. 3) Determine the intersection point of these two perpendicular bisectors (one from each set). 4) Verify if the intersection point serves as the center of a circle where the minimum and maximum distances from all points to this center correspond to the points chosen in step 1). 5) If the condition in step 4) holds true, then the intersection point becomes the center of the circle closest to the points, with its radius calculated as half the difference between the maximum and minimum distances plus the minimum distance."

The overall worst case time complexity comes out to be O(n^5). I have found a way to reduce the average case time complexity by utilizing the fact that the outer most 2 point out of the final 4 point that we get will always lie on the Convex hull but the worst case time complexity still remains the same.

Here is the

Code

A sample image where i have random point and with the minimum distance circle.

Is there any way that i can reduce the time complexity?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Ruudddiiii (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So the problem is to find a ring-shaped area with the minimum width (difference of outer and inner radius) which contains all the given points. In general, it's not true that the optimal solution must contain 2 points on the outer and 2 points on the inner boundary, even if they are in the general position. However, it is true that:

  • If all points lie on a single circle, that circle is the solution
  • Otherwise, the optimal ring has at least one point on the outer, and one on the inner boundary.

If you look at some candidate solution which has one point on the outer, and one on the inner boundary, you'll notice that when you pivot around those two points, keeping the ring width constant, eventually either the inner or the outer boundary will hit a point. Therefore, it is sufficient to check all triplets of points so that either 2 of them are on the inner, or 2 are on the outer boundary. A special case arises if the line connecting the two points contains the ring center, then, pivoting around while keeping the ring width constant is not possible, so you must also check all ordered pairs.

It may even be possible to do some kind of sweeping technique to lower the complexity to somewhere around $$$O(n^3 \log n)$$$.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think when we have n>=4 we will always have at least 2 point on inner and 2 point on outer ring.

    → Reply