ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ilia Kantor                          2:5020/1815.6  01 Dec 2001  06:01:28
 To : Michael Nemtsev
 Subject : Задачка: Точки на плоскости
 -------------------------------------------------------------------------------- 
 

 А вот я и до тебя добрался, Mr Michael Nemtsev!
 
  MN> Плоскость заполнена точками со случайными координатами (количество точек
  MN> конечно). Ограничить их окружностью с минимальным радиусом.
 
  MN> Каковы будут идеи?
     This circle is often called the minimum spanning circle.  It can be
     computed in O(n log n) time for n points.  The center lies on
     the furthest-point Voronoi diagram.  Computing the diagram constrains
     the search for the center.  Constructing the diagram can be accomplished
     by a 3D convex hull algorithm; for that connection, see, e.g.,
     [O'Rourke (C), p.195ff].
 
        'Почти такую' окpужность можно вычислить за o(n).
                         <O> Bye, Michael <O>
 --- GoldEd 3.00.Alpha4+
  * Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Задачка: Точки на плоскости   Michael Nemtsev   30 Nov 2001 12:36:50   Задачка: Точки на плоскости   Ilia Kantor   01 Dec 2001 06:01:28   Задачка: Точки на плоскости   Nickita A Startcev   02 Dec 2001 19:39:00   Задачка: Точки на плоскости   Boris Sivko   03 Dec 2001 21:57:39   Re: Задачка: Точки на плоскости   Sergey Politov   04 Dec 2001 21:06:16