ковали совместную работу. Рабин и Карп описали свой алгоритм в [117]; Бойер и Мур - в [32]. Галил и Сейферас [78] предложили интересный детерминированный алгоритм для поиска подстрок, работающий за линейное время и использующий лишь 0(1) памяти (помимо памяти для хранения образца и текста).

Вычислительная геометрия

Вычислительная геометрия - это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в машинной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задаче могут быть множество точек, набор отрезков, многоугольник (заданный, например, списком своих вершин в порядке движения против часовой стрелки) и т.п. Результатом может быть либо ответ на какой то вопрос (типа «пересекаются ли эти прямые?»), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, содержащий заданные точки).

В этой главе мы будем рассматривать только планиметрические задачи и проиллюстрируем некоторые важные методы вычислительной геометрии на этом примере. В наших задачах исходными данными будет множество точек плоскости {р{\ , заданных своими координатами: рг- = (жг-, уг), где жг-, уг- £ KL Например, га-угольник Р можно задать последовательностью (po,pi,p2, ,pn-i) его вершин в порядке обхода.

В разделе 35.1 мы разберём простейшие задачи об отрезках (в какую сторону мы поворачиваем, двигаясь по ломаной, составленной из двух отрезков? пересекаются ли два отрезка?) и эффективные методы их решения. В разделе 35.2 мы применим так называемый «метод движущейся прямой» и построим алгоритм, определяющий за время О (га lgra), есть ли среди га отрезков хотя бы два пересекающихся. В разделе 35.3 изложены два алгоритма, использующие «вращающуюся прямую» для вычисления выпуклой оболочки множества га точек: просмотр Грэхема, требующий времени О (га lgra), и проход Джарвиса, время работы которого О (га/г), где h - число вершин выпуклой оболочки. В разделе 35.4 рассмотрен алгоритм, который методом «разделяй и властвуй» за время О (га lgra) находит пару ближайших точек среди га заданных точек плоскости.

35.1. Свойства отрезков

Начнем с некоторых определений, связанных с отрезками. Выпуклой комбинацией (convex combination) двух различных точек р1 = (xi,yi) и р2 = (2:2,2/2) будем называть любую точку рз = (%з,Уз), Для которой х3 = ахг + (1 - а)х2 и у3 = ауг + (1 - а)у2 при некотором 0 а 1. Это же условие можно записать как р3 = api + (l - а)р2. Заданная таким образом точка рз принадлежит отрезку соединяющему pi и р2 (и может совпадать с одним из концов). Это свойство можно принять за определение отрезка, назвав отрезком (line segment), pTpi множество всех выпуклых комбинаций pi и р2. Точки pi и р2 называют концами (endpoints) отрезка. Если важен порядок концов,говорят об ориентированном отрезке (directed segment) рТр. Если pi совпадает с точкой (0,0), называемой началом координат (origin), то ориентированный отрезок рТр называют вектором (vector) Р2.

Нас интересуют такие вопросы:

1.Даны два ориентированных отрезка popt и роРг* с общим началом ро. В какую сторону (по часовой стрелке или против неё) надо повернуть отрезок pep! вокруг ро, чтобы он пошёл в направлении Рор2? (Имеется в виду меньший из двух поворотов.)

2.Даны ломаная Р1р2рз, составленная из двух отрезков pTpi и Р2Р3. Идя по ней от pi к рз, в какую сторону мы поворачиваем у р2 - налево или направо?

3.Пересекаются ли отрезки pTpi и pipj?

Мы сможем ответить на каждый из этих вопросов за время 0(1), что, впрочем, не удивительно, поскольку исходными данными в каждом случае является фиксированное число точек. Более важно то, что наши методы не будут использовать ни деления, ни тригонометрических функций - операций, которые сложнее и более чувствительны к ошибкам округления, чем используемые нами сложение, вычитание, умножение и сравнение. Например, если (отвечая на вопрос номер 3) действовать наиболее очевидным способом и искать уравнения прямых, содержащих данные отрезки, в виде у = тхА-Ь (то - угловой коэффициент, Ь - ордината точки пересечения прямой с осью у), затем точку пересечения прямых, а затем проверять, принадлежит ли найденная точка обоим отрезкам, то понадобится деление, и для почти параллельных отрезков возможны сложности, вызванные округлением при делении на близкое к нулю число. (Мы укажем способ, позволяющий избежать деления.)

Векторное произведение

Наше основное средство - понятие векторного произведения. Пусть даны вектора pi и р2 (рис. 35.1 (а)). Нас интересуют только вектора, лежащие в одной плоскости, поэтому под векторным