|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Boris Sivko 2:452/26.14 08 Dec 2001 03:41:45
To : Serge Kanilo
Subject : Задачка: Точки на плоскости
--------------------------------------------------------------------------------
Отвечать на письмо на тему "Re: Задачка: Точки на плоскости" очень просто.
Это уже сделал Serge Kanilo. о вот когда часы пробили ровно 01:34, а календарь
показывал Среда Декабрь 05 2001, настала моя очередь:
MN>>>> Плоскость заполнена точками со случайными координатами
MN>>>> (количество точек конечно). Ограничить их окружностью с
MN>>>> минимальным радиусом.
>> BS>> А как доказать, что это не эвристика?
>> SK> Hе знаю как, но тестовая программа работает быстро. Если
>> SK> честно, то оставление всех точек я нащупал, посмотрев
>> SK> несколько первых шагов пробного алгоритма.
BS>> Hе нравятся мне такие реализации. Они похожи за сплошное
BS>> залатывание дыр и никогда до конца не уверен, что всё работает
BS>> правильно. Такие алгоритмы пригодны разве что для того, чтобы
BS>> находило более менее подходящий вариант.
Пока рассуждения у меня такие:
Докажем, что искомая ок-сть проходит как минимум через 2 точки. Если ок-ть не
проходит через точки, то сл-но её радиус можно умеьшить по крайней мере так,
чтобы ок-сть проходила через одну точку. Если ок-сть проходит через одну точку,
то её центр можно сместить так, чтобы окружность проходила через 2 точки.
Через центр ок-сти и серединой отрезка 2 точек ок-сти проведём прямую. Есс-но
можно сделать вывод, что ответ в любом случае будет иметь центр на этой прямой.
Смещая его на dx, можно либо переместить ок-сть так, чтобы 2 точки лежали на
диаметре полученной, либо нам это не даст сделать 3-я точка, лежащая вне ок-сти,
построенной на диаметре 2-х.
Вывод: если решать на этой стадии перебором, то нужно перебрать все пары и все
тройки точек. И решение будет правильным.
Только вот сложность осталась высокой. Как её сделать до O(N log N) без
понятия, т.к. велосипед в англоязычной литературе искать негде.
Счастливо, Serge. Вспоминай обо мне...
... I'll be back...
* Origin: 2ЗТ - любой необратимый процесс в природе необратим. (2:452/26.14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Задачка: Точки на плоскости