35.11

(К упр. 35.3-4)

(a)Звёздный многоугольник: из точки р видна любая точка его границы.

(b)Многоугольник, не являющийся звёздным. Слева закрашена тень точки q, справа - тень точки ql. Ядро пусто, так как эти области не пересекаются.

35-3.4

Пусть даны многоугольник Р и точка q на его границе. Тенью (shadow) точки q называется множество всех точек г, для которых что отрезок qf не выходит за пределы многоугольника Р. Многоугольник Р называется звёздным (star-shaped), если внутри него есть точка р, из которой видна вся его граница (другими словами, р принадлежит тени любой точки границы многоугольника Р). Множество всех таких точек р называется ядром (kernel) многоугольника Р (см. рис. 35.11). Даны вершины зв/здного га-угольника Р, перечисленные в порядке обхода границы против часовой стрелки. Покажите, как можно найти СН(Р) за время 0(п).

35.3-5

Задача об отыскании выпуклой оболочки множества Q в режиме «on-line» (on-line convex-hull problem) состоит в следующем: нам дают га точек одну за другой; в каждый момент времени мы должны указать выпуклую оболочку всех точек, полученных к этому моменту. Можно применить проход Грэхема на каждом шаге заново, и тогда общее время работы алгоритма будет равно О (га2 lgra). Придумайте алгоритм, требующий времени О (га2).

35.3-6*

Используя просмотр точек слева направо, найдите выпуклую оболочку га точек за время О (га lgra).

35.4. Отыскание пары ближайших точек

Пусть теперь нам надо найти среди га 2 точек множества Q пару ближайших друг к другу точек. Расстояние между точками понимается в обычном смысле: точки р\ = (x\,yi) н р2 = (2:2,2/2) находятся на расстоянии у7(х\ - х2)2 + (у\ - У2)2

Вообще говоря, две точки могут совпадать (тогда расстояние между ними равно 0). Такая задача может возникнуть, например, в системах контроля за транспортом: полезно знать, какие два транспортных средства ближе всего друг к другу (риск столкновения)

Если искать пару ближайших точек «в лоб», надо перебрать все С2 = 0(га2) пары точек. В этом разделе мы с помощью метода

«разделяй и властвуй» построим алгоритм, время работы которого описывается рекуррентным соотношением Т(п) = 2Т(га/2) + 0(га), т.е. равно О (га lgra).

Метод «разделяй и властвуй» для отыскания ближайших точек.

Входные данные каждого рекурсивного вызова алгоритма состоят из подмножество Р С Q и двух массивы X и У. Каждый из массивов содержит точки подмножества р, но порядок в них разный: в массиве X точки расположены в порядке возрастания абсцисс, а в массиве У - в порядке возрастания ординат. Заметим, что мы не можем позволить себе сортировать точки при каждом вызове, так как в этом случае получится соотношение (как минимум) Т(п) = 2Т(п/2) +0(ralgra), т.е. Т(п) = 0(га1п2 га). (Мы увидим, как эту трудность можно обойти с помощью «предсортировки».

Итак, пусть мы получили Р,Х и У. Если \Р\ 3, перебираем все пары точек (максимум три) и сравниваем расстояние. Если же \Р\ > 3, мы поступаем так:

Разделяй (divide): Находим вертикальную прямую /, которая делит множество Р на два подмножества Pl и Pr половинного размера (\Рь\ = П-Р/2], \Pr\ =точки, лежащие на прямой /, как-то поделены между Pl и Pr). Массив X делим на массивы Xl и Xr, содержащие точки подмножеств Pl и Pr (сохраняя порядок); массив У делится на массивы Yl и Yr аналогичным образом.

Властвуй (conquer): После деления Р на Pl и Pr, выполняем два рекурсивных вызова и находим пару ближайших точек в множестве Pl (входные данные этого вызова - подмножество Pl и массивы Xl и Yl), а также пару ближайших точек в множестве Pr (входные данные - Pr, Xr и Yr). Обозначим расстояния между ближайшими точками в подмножеств Pl и Pr через Sl и Sr. Положим S = min (Sl, deltaR).

Соединяй (combine): Для всего множества Р парой ближайших точек является либо одна из найденных пар точек (расстояние S), либо некоторая «приграничная» пара точек, в которой одна точка принадлежит множеству Pl, а другая - Pr (если среди таких пар есть пара с расстоянием меньше S). Очевидно, что точки такой приграничной пары отстоят от прямой / не более, чем на S, т.е. находятся в симметричной относительно / вертикальной пограничной полосе шириной 2S (рис. 35.12 (а)). Чтобы найти такую приграничную пару, если она существует, проделаем следующее.

1.Создадим массив У/, поместив в него все точки из массива У, которые попадают в пограничную полосу (с той или иной стороны от прямой /). (Порядок сохраняем: массив У/ отсортирован по ординатам точек.)

2.Для каждой точки р массива Y ищем такие точки массива У, которые удалены от р не более, чем на S. Как мы вскоре увидим, достаточно рассмотреть только 7 соседних (в порядке возрастания ординат) точек в массиве У. Мы вычисляем расстояние от р

до каждой из этих 7 точек. Выполнив это для всех точек р из У, находим 8/ - расстояние между точками массива У/, расположенными ближе всего друг к другу.

3. Если 8 < 8, то пара ближайших точек находится внутри вертикальной полосы и мы возвращаем эту пару точек и расстояние 5. В противном случае мы возвращаем пару, найденную при одном из рекурсивных вызовов, и расстояние 8.

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

Правильность алгоритма

Нужно понять лишь, почему достаточно сравнивать каждую точку полосы лишь с семью следующими за ней (в порядке возрастания ординаты). Сейчас мы в этом убедимся.

Пусть (при некотором вызове) ближайшей парой точек является пара из точек pl £ Pl и рд £ Рд (рис. 35.12 (а)), и расстояние 8 между этими точками строго меньше 8. Точка pl должна находиться слева от / на расстоянии не более 8 (или на самой прямой); рд - справа на расстоянии не большем 8 (или на прямой). Кроме того, расстояние по вертикали между pl и рд также не превосходит 8. Следовательно (рис. 35.12 (а)), точки pl и рд можно поместить в прямоугольник размера 8x28, симметричной относительно прямой /. (Конечно, в него могут попасть и другие точки.)

Покажем теперь, что внутри этого прямоугольника может быть не более 8 точек из множества Р. Рассмотрим его левую половину - квадрат 8x8. Все точки из Pl находятся на расстоянии не менее 8 друг от друга, поэтому в этом квадрате может быть максимум 4 таких точки (в каждой его четвертинке может быть не более одной точки), см. рис. 35.12 (Ь). В правой половине прямоугольника (не считая границы) точек из Pl быть не может, так что всего в прямоугольнике не более 4 точек из Pl - По аналогичным причинам там не более 4 точек из Рд. Заметим, что случай 8 точек действительно возможен: четыре точки из Pl могут быть в углах левого квадрата, а четыре точки из Рд - в углах правого (две точки будут общими для Pl и -Рд). а Теперь ясно, что что для каждой точки достаточно проверить 7 точек, непосредственно следующих за ней в массиве У: если между двумя ближайшими точками есть ещё 7 промежуточных (в порядке возрастания ординат), то все 9 точек попадут внутрь прямоугольника, а этого быть не может, как мы видели.

Детали реализации и время работы алгоритма.

Наша цель - получить для времени работы алгоритма рекуррентное соотношение Г(га) = 2Г(га/2) + 0(п) (здесь Г(га) - время обработки га точек). Чтобы этого достичь, мы должны предполагать, что входные массивы X и У отсортированы по абсциссе и ординате соответственно (тогда разделить множество на левую и