|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 05 Dec 2001 19:07:18
To : All
Subject : Точки на плоскости.
--------------------------------------------------------------------------------
Hi, All.
> Плоскость заполнена точками со случайными координатами
> (количество точек конечно). Ограничить их окружностью с
> минимальным радиусом.
Hу сколько можно изобретать велосипед. Эта задача уже давно решена.
------------------------
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]. For direct algorithms, see:
S. Skyum, "A simple algorithm for computing the smallest enclosing
circle"
Inform. Process. Lett. 37 (1991) 121--125.
J. Rokne, "An Easy Bounding Circle" [Gems II] pp.14--16.
-----------------------
WBR, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
