Построение окружности с минимальным радиусом

Shtirlitz · Сообщение **Shtirlitz** » 30 окт 2011, 16:32

Добрый вечер, товарищи! Не могли бы вы подсказать идею решения следующей задачи?

Дано n точек на плоскости. Нужно построить окружность таким образом, чтобы она охватывала все эти точки, лежащие на плоскости, и чтобы радиус её был минимальным.

И здесь требуется алгоритм, который будет решать эту задачу за линейное время.

Подскажите, пожалуйста, с чего здесь нужно начать. Заранее спасибо!

MrDindows · Сообщение **MrDindows** » 30 окт 2011, 17:14

Очевидно, что на искомой окружности будут лежать какие-то три точки ( или две, если они будут лежать на диаметре окружности). Поэтому можно перебрать все комбинации из трёх точек, для каждой находить центр окружности описанной вокруг треугольника из этих трёх точек, и проверять, лежат ли остальные точки в этой окружности. Ну и, в принципе, это всё можно оптимизировать немного.

Вот такая у меня идея алгоритма, правда не могу сказать будет ли он решать задачу за линейное время, но мб это вам чем-то поможет=)

vicvolf · Сообщение **vicvolf** » 30 окт 2011, 17:50

Если для 1 точки взять расстояние до нее это будет 0 и записать в матрицу, для второй аналогично и.т.д. Следовательно на диаганали матрицы будут стоять нули. В остальном матрица симметрическая, поэтому все расстояния определять не надо. Поэтому исходные данные можно представить в виде треугольном матрицы с n(n-1)/2 элементами. Поэтому задача заключается в поиске максимального из (n-1)/2 элементов. Например дихотомический алгоритм поиска даст $log_2 \frac {n(n-1)} {2}$ -это уже алгоритм линейной трудоемкости.

mihailm · Сообщение **mihailm** » 30 окт 2011, 18:06

vicvolf писал(а):Source of the post
Надо найти 2 точки, лежащие на максимальном расстоянии и соединить их-это будет диаметр искомой окружности.

Треугольник со сторонами 4,3,3

vicvolf · Сообщение **vicvolf** » 30 окт 2011, 18:42

mihailm писал(а):Source of the post
vicvolf писал(а):Source of the post
Надо найти 2 точки, лежащие на максимальном расстоянии и соединить их-это будет диаметр искомой окружности.

Треугольник со сторонами 4,3,3

Да максимальное расстояние не проходит.

OpenGL · Сообщение **OpenGL** » 30 окт 2011, 20:34

Это известная задача о нахождении наименьшей охватывающей окружности. тут вроде описан линейный алгоритм. На русском есть описание алгоритма тут, но он не линейный

Shtirlitz · Сообщение **Shtirlitz** » 31 окт 2011, 22:22

Спасибо всем большое за помощь! Попробую разобраться.

На русском есть описание алгоритма тут, но он не линейный

а какая трудоёмкость будет у этого алгоритма тогда?

vicvolf · Сообщение **vicvolf** » 01 ноя 2011, 07:34

Shtirlitz писал(а):Source of the post
а какая трудоёмкость будет у этого алгоритма тогда?

Больше, чем у линейного!

Equinoxe · Сообщение **Equinoxe** » 01 ноя 2011, 12:44

Shtirlitz писал(а):Source of the post
Добрый вечер, товарищи! Не могли бы вы подсказать идею решения следующей задачи?

Дано n точек на плоскости. Нужно построить окружность таким образом, чтобы она охватывала все эти точки, лежащие на плоскости, и чтобы радиус её был минимальным.

И здесь требуется алгоритм, который будет решать эту задачу за линейное время.

Подскажите, пожалуйста, с чего здесь нужно начать. Заранее спасибо!

Сам алгоритм я к сожалению точно не помню, но могу сказать про него, что:
1. он рандомизированный
2. его оценка доказывается по индукции
3. суть его в том, что в каждый момент есть какие-то выбранные (что-то не более 3х) точки и некоторая окружность, алгоритм пытается достроить конструкцию и в некотором случае начинает всё почти заново
Сейчас попробую загуглить его, но вообще считается, что он вполне придумываем

А вот и весь алгоритм:

Алгоритм рекурсивный, за аргументы он берет два множества точек S и Q. Он считает минимальную окружность для S и Q, считая, что каждая точка Q лежит на границе возможной минимальной окружности. Так, сама задача решается вызовом алгоритма с S=исходным точкам, а Q — пустому множеству. Т.к. алгоритм вызывает себя рекурсивно, он будет увеличивать Q пока он не будет содержать все граничные точки окружноти.
Алгоритм обрабатывает точки S в случайном порядке, поддерживая множество P обработанных точек и минимальную окружность, охватывающую P и Q. На каждом шаге алгоритм проверяет, входит ли очередная точка r в окружность, если нет, то алгоритм заменяет текущую окружность на результат алгоритма со множествами P и Q+r. Независимо от того, изменилась окружность или нет, r включается во множество P. Обработка каждой точки, таким образом, состоит из проверки за константное время, лежит ли точка в окружности, и возможно ещё один рекурсивный вызов алгоритма. Можно показать, что i-тая точка имеет вероятность рекурсивного вызова O(1/i), и таким образом время линейно

(Правда мне нерекурсивный вариант рассказывали)

Shtirlitz · Сообщение **Shtirlitz** » 07 ноя 2011, 01:25

Если для 1 точки взять расстояние до нее это будет 0 и записать в матрицу, для второй аналогично и.т.д. Следовательно на диаганали матрицы будут стоять нули. В остальном матрица симметрическая, поэтому все расстояния определять не надо. Поэтому исходные данные можно представить в виде треугольном матрицы с n(n-1)/2 элементами. Поэтому задача заключается в поиске максимального из (n-1)/2 элементов. Например дихотомический алгоритм поиска даст -это уже алгоритм линейной трудоемкости.

А не могли бы вы немного пояснить на этом примере, как мы здесь считаем трудоёмкость? Почему логарифм берём?...

yourdomain.com