Решение задачи 17.
Переформулируем задачу: На плоскости своими координатами задаются N точек Pi(xi,yi). Построить окружность минимального радиуса с центром на оси абсцисс так, чтобы она содержала внутри себя и на своей границе все эти точки.
Везде в дальнейшем будем обозначать через C(P,Z) окружность с центром в точке (P,O) и проходящую через точку Z=(Zx,Zy).
Очевидно, что на искомой окружности лежит по меньшей мере одна точка. Действительно, в противном случае мы можем, не меняя центра окружности, уменьшить ее радиус, а это противоречит предположению о том, что нами была построена окружность минимального радиуса.
Докажем следующее простое утверждение: Если на искомой окружности лежит единственная точка, то центр окружности есть проекция этой точки на ось абсцисс.
Предположим противное - на минимальной окружности лежит единственная точка Z(Zx,Zy), а центр ее не совпадает с (Zx,0). Если мы начнем понемножку двигать центр окружности, проходящей через точку Z, в направлении (Zx,0), то, так как все точки, кроме Z, лежат внутри окружности, до какого-то момента они и будут оставаться внутри нее. Таким образом мы можем хоть чуть-чуть, но сдвинуть центр, уменьшив при этом радиус окружности, содержащей все точки. Получаем противоречие с предположением о минимальности радиуса.
Следствие. Если на искомой окружности лежит только одна точка, то это точка с максимальной по модулю ординатой.
Отметим далее, что окружность с центром на оси абсцисс
единственным образом определяется двумя лежащими на ней точками (центр этой окружности - это точка пересечения оси абсцисс и срединного перпендикуляра к отрезку, соединяющего эти две точки).
Таким образом мы получаем следующий
Алгоритм 1:
Шаг 1.Ищем точку (xi,yi) с максимальной по модулю ординатой yi (если таких точек несколько, и у них разные абсциссы, то перейти на Шаг 2), и для окружности C(xi,(xi,yi)) проверяем, содержит ли она все N точек. Если да, то задача решена, если нет, то
Шаг 2. Среди окружностей, определяемых всевозможными парами точек (Pi, Pj), находим те, которые содержат все точки, а затем выбираем из них окружность минимального радиуса.
Пар точек, которые могут определять окружности, всего N(N-1)/2, т.е. порядка N*N, следовательно, и возможных окружностей тоже порядка N*N. Для проверки принадлежности N точек каждой окружности требуется порядка N операций. Получаем, что сложность этого алгоритма порядка N3. (Когда мы говорим о сложности алгоритма, то мы рассматриваем только зависимость роста числа требуемых операций от числа N, игнорируя все константные множители и медленно растущие слагаемые).
Рассмотрим другой способ решения этой задачи, основанный
на более глубоком ее анализе.
Вариант #2.
Проверка по Шагу 1 ранее изложенного алгоритма остается без изменения. Пусть искомая окружность не найдена.
Для обоснования Шага 2 докажем следующее утверждение: Пусть окружность с центром (Pij,0) определяется точками
Pi(xi,yi) и Pj(xj,yj). Она только тогда может быть содержащей все точки окружностью C минимального радиуса, когда (Pij,0) лежит на ортогональной проекции отрезка [(xi,yi),(xj,yj)] на ось абсцисс, т.е. должны выполняться неравенства xi<=Pij<=xj.
Окружность C с центром (Pij0) должна проходить не менее чем через 2 точки заданного множества из N точек, и при этом из этих точек всегда можно выбрать две такие (обозначим их Pi(xi,yi) и Pj(xj,yj)), что xi<Pij<xj. Действительно, если бы абсциссы всех лежащих на окружности точек были, например, меньше Pij, то (Pij,0) можно было бы сместить влево по оси абсцисс на некоторую величину с уменьшением радиуса охватывающей все точки окружности, что противоречит минимальности найденной ранее окружности.
Ни одна из точек, лежащих на окружности не может иметь абсциссы Pij вследствие невыполнения условия Шага 1.
Итак: всегда можно найти две лежащие на окружности точки Pi и Pj с абсциссами, соответственно, меньше и больше абсциссы центра окружности. Эти точки определяют центр окружности (Pij,0) - точку пересечение серединного перпендикуляра к отрезку [Pi,Pj] с осью абсцисс. При этом точка (Pij,0), естественно, будет лежать на проекции отрезка [Pi,Pj] на ось абсцисс.
Рассматривая все пары точек (Pi,Pj) таких, что точка пересечения (Pij,0) серединного перпендикуляра к отрезку [Pi,Pj] с осью абсцисс лежит на проекции отрезка [Pi,Pj] на ось абсцисс, получаем, что центр искомой окружности минимального радиуса совпадает с одной из таким образом полученных точек. Каждая из рассматриваемых пар точек (Pi,Pj) определяет окружность минимального радиуса Rij, содержащую эти две точки.
Из всего вышесказанного получаем, что интересующая нас окружность минимального радиуса, содержащая N точек, должна
иметь максимальный из всех полученных радиусов Rij.
Всего пар точек (Pi,Pj) не более (N2-N)/2, и, следовательно, сложность алгоритма
O((N2-N)/2) = O(N2-N) = O(N2).
Тут мы, как и обычно, избавляемся от констант и медленно растущих слагаемых.
Вариант #3.
Все вычисления на машине проводятся с ограниченной точностью, с определенным числом знаков после запятой. Поэтому нам бывает достаточно только указать, что интересующая нас точка лежит внутри отрезка заранее заданной длины epsilon. Epsilon задается пользователем. Например, если мы хотим найти координату точки с точностью 5 знаков после запятой, то epsilon = 10-6.
В отличие от варианта #2 мы не будем брать все перпендикуляры, попадающие на проекции отрезков и искать среди получаемых окружностей окружность с максимальным радиусом. Наоборот, описанным ниже способом будем выбирать точку на оси абсцисс и проверять, является ли она искомой или нет.
Из варианта решения #2 можно сделать вывод, что искомая точка лежит на отрезке [A0,B0]=[min{xi},max{xi}]. Пусть C0=(A0+B0)/2 - середина этого отрезка, а L=B0-A0 его длина.
Обозначим:
D1(C0)=максимальное из расстояний от точки (C0,0) до точек (xi,yi) с абсциссами xi<=C0;
Dr(C0)=максимальное из расстояний от точки (C0,0) до точек (xi,yi) с абсциссами xi>=C0.
i-ый итеративный (повторяющийся) шаг алгоритма, i=0, 1, 2, 3, ... :
Если Bi-Ai<=epsilon, то центр окружности лежит на отрезке [Ai,Bi] и желаемая точность достигнута. Стоп.
Иначе
Вычисляем Ci=(Ai+Bi)/2.
Находим Dl(Ci) и Dr(Ci).
Если Dl(Ci)<Dr(Ci), то искомая точка не может лежать на промежутке [Ai,Ci), так как радиус любой содержащей N точек окружности с центром на этом промежутке больше Dr(Ci) (проверьте сами!), а окружность с центром Ci имеет радиус Dr(Ci). Поэтому центр искомой окружности лежит на [Ci,Bi], который мы обозначим [Ai+1,Bi+1],
иначе, если Dr(Ci)<Dl(Ci), то, аналогично, получаем, что центр искомой окружности лежит на [Ai,Ci], которой мы обозначим [Ai+1,Bi+1]
иначе, если Dr(Ci)=Dl(Ci),
то Ci - центр искомой окружности. Стоп.
Конец i-го итеративного шага. Выполнить шаг i+1.
Мы видим, что длина L начального отрезка на каждом шаге уменьшается вдвое. Алгоритм, вообще говоря, заканчивает работу при выполнении условия
L/(2S)<=epsilon,
т.е. требуется не более чем S=[log2 (L/epsilon)]+1 шагов, где log2 - это логарифм по основанию 2.
Так как на каждом шаге (для вычисления Dl и Dr) выполняется не более O(N) операций, то всего их потребуется порядка O(N log2 (L/epsilon)).
|
