Smallest Enclosing Circle/Sphere Problem

Правка en6, от hongjun-7, 2016-02-15 06:36:13
  1. Smallest Enclosing Circle : 2-Dimension Problem (Written in Korean. Output values are smallest enclosing circle's position on first line and radius on second line.)

  2. Smallest Enclosing Sphere : 3-Dimension Problem

Thesis Link

Let P(X, Y, Z) = (Average(x(i)), Average(y(i)), Average(z(i)))

Average(x(i)) = Sum(x(i)) / N

Average(y(i)) = Sum(y(i)) / N

Average(z(i)) = Sum(z(i)) / N

P is inside of the points' convex hull.

Now find the farthest point(M) to P.

Move P toward M a little bit and the ratio should be small and decreasing.

If there is no such a movement, that is the answer.

Total Time Complexity is O(N * constant number)

(We can reduce 'N' by getting convex hull.)

My 2-Dimension Problem's Solution Code

My 3-Dimension Problem's Solution Code

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский hongjun-7 2016-02-17 11:16:00 8
en8 Английский hongjun-7 2016-02-15 06:37:26 10 Tiny change: 'n. Output values are smallest' -> 'n. Output is the smallest'
en7 Английский hongjun-7 2016-02-15 06:36:42 4 Tiny change: ' line and radius on' -> ' line and the radius on'
en6 Английский hongjun-7 2016-02-15 06:36:13 8 Tiny change: ' circle's x and y position ' -> ' circle's position '
en5 Английский hongjun-7 2016-02-15 06:35:17 5 Tiny change: 'blem/2626)\n\n(Written i' -> 'blem/2626) (Written i'
en4 Английский hongjun-7 2016-02-15 06:34:59 130
en3 Английский hongjun-7 2016-02-15 06:29:58 6
en2 Английский hongjun-7 2016-02-15 06:29:34 2 Tiny change: '/vju6Uh)\n[My 3-Di' -> '/vju6Uh)\n\n[My 3-Di'
en1 Английский hongjun-7 2016-02-15 06:29:10 963 Initial revision (published)