pacha2880's blog

Circle with minimum radius with all points inside
By pacha2880, history, 21 month(s) ago, In English

What is the best way to solve this problem?, I have a solution in $$$O(n^4)$$$

Given are $$$N$$$ points $$$(x_i, y_i)$$$ in a two-dimensional plane. Find the minimum radius of a circle such that all the points are inside or on it.

Link to the problem https://atcoder.jp/contests/abc151/tasks/abc151_f

thanks in advance.

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

I suppose you can use inversion (geometry).

The idea of inversion is that if you invert about a point $$$P$$$(using radius=1, but that only comes down to a constant difference), then a circle passing through that $$$P$$$ with radius $$$R$$$ becomes a straight line with distance $$$\frac{1}{2R}$$$ away from $$$P$$$, and the points inside the circle becomes the points on the opposite side of the line as $$$P$$$.

Find the convex hull of the $$$N$$$ points. Without loss of generality, suppose that the $$$N$$$ points are their own convex hull. For each point $$$P$$$ on the convex hull, we carry out inversion on the remaining $$$N-1$$$ points. Now we need to find a line farthest from the inversion center $$$P$$$ such that the line separates $$$P$$$ from the inverted $$$N-1$$$ points. To do this, we find the convex hull of these points again, and process each edge of the resulting hull. We seek the largest distance after using each of the $$$N$$$ points as inversion centers.

The time complexity should be $$$O(n^2 \log{n})$$$. Correct me if the algorithm is wrong; I'm not very familiar with this either.

Edit: As pointed out below, there are a variety of solutions as this is a known problem.

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

This is a well-known problem called minimum enclosing circle (it has also other names).

I personally use Welzl's algorithm for it with expected time complexity of $$$O(n)$$$.

Code
→ Reply