Существует множество точек на плоскости, заданных координатами (X,Y).
Подскажите плиз способ нахождения координат центра (CX,CY) и минимального радиуса (R) окружности,
которая включала бы в себя все эти точки.

Спасибо

Здравствуйте, LameFox, Вы писали:

LF>Существует множество точек на плоскости, заданных координатами (X,Y).
LF>Подскажите плиз способ нахождения координат центра (CX,CY) и минимального радиуса (R) окружности,
LF>которая включала бы в себя все эти точки.

Все сильно зависит от того, какая сложность вас устроит.

1. Дебильный вариант: перебираем все возможные пары точек как кандидатов
в диаметры, кроме того пробуем около всякой тройки точек описать окружность.
Время работы O(N^4). Никогда так не делайте!

2. Стандартный вариант: ну диаметры можно по-прежнему перебирать, это даст
O(N^3), а перебор троек можно оптимизировать. Именно фиксируем пару точек
A и B. Возможны два случая расположения центра -- в верхней относительно AB
полуплоскости и в нижней. Для каждого, случая рассмотрев оставшиеся точки,
несложно вычислить требования к радиусу окружности: оценки снизу и сверху.
Наконец еще за один проход можно выяснить, есть ли подходящая третья точка.
Получится сложность O(N^3), кроме того тут еще море возможностей для
оптимизаций и вариаций.

3. Если точек очень много.. ну тогда нам поможет диаграма Вороного.
Ссылка из Handbook of Theoretical Computer Science, vol A., p. 363,
sec. 6.3.3 "Smallest enclosing circle".
Smahos and Hoey [200] exhibited the first O(n log n) solution by
ovservising that the smallest enclosing circle is either determined by the diameter
of the set of centered at a vertex of the furthest-point Voronoi diagram.

Если интересно, что такое [200], то это:
Shamos, M.I. and D. Hoey, Closest-point problems, in: Proc. 16th IEEE Ann.
Symp. Found. Comput. Sci. (1975), 151-162

Здравствуйте, LameFox, Вы писали:

LF>Существует множество точек на плоскости, заданных координатами (X,Y).
LF>Подскажите плиз способ нахождения координат центра (CX,CY) и минимального радиуса (R) окружности,
LF>которая включала бы в себя все эти точки.

LF>Спасибо

см. http://www.inf.ethz.ch/personal/gaertner/miniball.html

Константин

Здравствуйте, klovetski, Вы писали:

K>см. http://www.inf.ethz.ch/personal/gaertner/miniball.html

Что-то не открывается

Здравствуйте, LameFox, Вы писали:

LF>Здравствуйте, klovetski, Вы писали:

K>>см. http://www.inf.ethz.ch/personal/gaertner/miniball.html

LF>Что-то не открывается

Открывается. Только что проверил. Можешь скачать все вместе (текст
программы на C с описанием в *.pdf формате ):
http://www.inf.ethz.ch/personal/gaertner/miniball/miniball.tar.gz

или попробуй

http://www.inf.ethz.ch/personal/gaertner/miniball/index.html

или

http://www.inf.ethz.ch/personal/gaertner/miniball/code
где выложены тексты программы.
Константин.

Здравствуйте, LameFox, Вы писали:

LF>Существует множество точек на плоскости, заданных координатами (X,Y).
LF>Подскажите плиз способ нахождения координат центра (CX,CY) и минимального радиуса (R) окружности,
LF>которая включала бы в себя все эти точки.

LF>Спасибо

Один из вариантов — посчитать центр масс системы, считая что все точки имеют равный вес.
А минимальный радиус — это минимальное расстояние между точкой и центром масс.
Сложность — О(N).

Здравствуйте, Sergeem, Вы писали:
S>Один из вариантов — посчитать центр масс системы, считая что все точки имеют равный вес.
S>А минимальный радиус — это минимальное расстояние между точкой и центром масс.
Ты, наверное, имел в виду максимальное расстояние между точкой и центром масс. Потому что иначе почти все точки будут лежать снаружи такой окружности.
S>Сложность — О(N).
Быстро, но неправильно. Давай сгруппируем все точки небольшой окрестности точки p0 радиусом r. На расстоянии L >> r от них разместим еще одну точку p1.
Центр масс будет находиться на расстоянии d < r от p0 (очевидно, что если это не так, то мы всегда сможем "докинуть" в эту окрестность еще точек, чтобы "перевесить" p1).
Данный алгоритм даст в качестве ответа ~L, т.к. это и есть максимальное расстояние от центра масс до точки. Но это, очевидно, неправильно — мы могли бы провести окружность радиусом ~L/2 при более разумном выборе расположения ее центра: на середине отрезхка p0-p1. Таким образом, найденная окружность — не самая маленькая из покрывающих все множество точек.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Sergeem, Вы писали:
S>>Один из вариантов — посчитать центр масс системы, считая что все точки имеют равный вес.
S>>А минимальный радиус — это минимальное расстояние между точкой и центром масс.
S>Ты, наверное, имел в виду максимальное расстояние между точкой и центром масс. Потому что иначе почти все точки будут лежать снаружи такой окружности.
S>>Сложность — О(N).
S>Быстро, но неправильно. Давай сгруппируем все точки небольшой окрестности точки p0 радиусом r. На расстоянии L >> r от них разместим еще одну точку p1.
S>Центр масс будет находиться на расстоянии d < r от p0 (очевидно, что если это не так, то мы всегда сможем "докинуть" в эту окрестность еще точек, чтобы "перевесить" p1).
S>Данный алгоритм даст в качестве ответа ~L, т.к. это и есть максимальное расстояние от центра масс до точки. Но это, очевидно, неправильно — мы могли бы провести окружность радиусом ~L/2 при более разумном выборе расположения ее центра: на середине отрезхка p0-p1. Таким образом, найденная окружность — не самая маленькая из покрывающих все множество точек.

Да, погорячился я.
Жалко, самому себе нельзя -1 поставить