Nuu's blog

Smallest circle set points [Help]

By Nuu, 9 years ago, In English

Hi guys, i'm trying solve this problem.

The resume is: given a set of points, print the smallest circle that cover all points.

I'm searching, but only find aproximate algorithms.

Somebody know a algoritm without aproximate?

Thanks for advice.

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

»
9 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Hi, I believe that this can help you out. :D

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

    this approach gets WA because fail in coordinates approximation :/

    → Reply
»
9 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Exact algorithms are described in Smallest-circle problem.

Best wishes

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

On a side note see this problem too . A slightly modified version of smallest enclosing circle : https://www.codechef.com/problems/CHEFCIRC

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

You can use nested ternary search though it is O(nlogC^2)

→ Reply