Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 221
Текст из файла (страница 221)
Как показано в разделе 9.1, если каждая операция сравнения выполняется в течение времени О (1), то выбор минимального из и значений занимает время 0 (и). Таким образом, обход по Джарвису длится в течение времени 0 (пй). УПРажНЕНИЯ 33.3-1. Докажите, что в процедуре ОкАнлм Бслн точки р1 и р должны быть вершинами СН Я). 33.3-2. Рассмотрим модель вычислений, которая поддерживает сложение, сравнение и умножение и в которой существует нижняя граница времени сортировки и чисел, равная й (п1яп).
Докажите, что в такой модели й (и! ли) — нижняя граница времени вычисления вершин выпуклой оболочки множества и точек в порядке их обхода. 33.3-3. Докажите, что в заданном множестве точек Я две самые удаленные друг от друга точки должны быть вершинами СН (Я).
33.3-4. Для заданного многоугольника Р и точки д на его границе тенью (злаботч) точки д называется множество точек г, для которых отрезок 9г полностью находится на границе или во внутренней области многоугольника Р. Многоугольник Р называется звездоодразиым (зшг-зларед), если в его внутренней области существует точка р, которая находится в тени любой точки, лежащей на границе этого многоугольника. Множество всех таких точек называется ядром (кегле1) многоугольника Р. На рис.
33.10 приведены примеры двух многоугольников. В части а показан звездообразный многоугольник. Отрезок, соединяющий точку р с любой из принадлежащих границе многоугольника точек д пересекает эту границу только в точке д. В части б рисунка приведен многоугольник, не являющийся звездообразным.
Выделенная серым цветом левая область является тенью точки 9, а выделенная правая область — тенью точки д'. Поскольку эти области не перекрываются, ядро является пустым. Пусть звездообразный и-угольник Р задан своими вершинами, перечисленными в порядке обхода против часовой стрелки.
Покажите, как построить СН (Р) за время 0 (и). Часть ЧП. Избранные темы 1074 6) а) Рис. 33.10. Определение звездообразного многоугольника, о котором идет речь в упражнении 33.3-4 33.3-5. В олератаеной задаче о выпуклой оболочке (оп-1ше сопчех-Ьп!1 ргоЬ1еш) параметры каждой из и точек из заданного множества Я становятся известны по одной точке за раз.
После получения сведений об очередной точке строится выпуклая оболочка тех точек, о которых стало известно к настоящему времени. Очевидно, можно было бы применять сканирование по Грэхему к каждой из точек, затратив при этом полное время, равное 0 (пз 1кп). Покажите, как решить оперативную задачу о выпуклой оболочке за время О (тР).
* 33.3-6. Покажите, как реализовать инкрементный метод построения выпуклой оболочки таким образом, чтобы время его работы было равно 0 (и 1я и). 33.4 Поиск пары ближайших точек Теперь рассмотрим задачу о поиске в множестве Я, состоящем из и > 2 точек, пары ближайших друг к другу точек. Термин "ближайший" относится к обычному евклидову расстоянию: расстояние между точками р) = (х), у)) и рз = (хз, уз) равно . Две точки в множестве Я могут совпадать; в этом случае расстояние между ними равно нулю. Эта задача находит применение, например, в системах управления транспортом. В системе управления воздушным или морским транспортом может понадобиться узнать, какие из двух транспортных средств находятся друг к другу ближе всего, чтобы предотвратить возможное столкновение между ними.
В алгоритме, который работает "в лоб", просто перебираются все (~) = О (пз) пар точек. В данном разделе описывается решение этой задачи с помощью алгоритма разбиения. Время решения этим методом определяется знакомым рекуррентным соотношением Т(т)) = 2Т(п/2) + О (и). Таким образом, время работы этого алгоритма равно 0 (и 1я и).
Глава 33. Вычислительная геометрия 1075 Алгоритм декомпозиции В каждом рекурсивном вызове описываемого алгоритма в качестве входных данных используется подмножество Р Я~ и массивы Х и У, в каждом из которых содержатся все точки входного подмножества Р. Точки в массиве Х отсортированы в порядке монотонного возрастания их координаты х. Аналогично;,массив У отсортирован в порядке монотонного возрастания координаты у. Заметим, что достигнуть границы 0 (и!ли) не удастся, если сортировка будет производиться в каждом рекурсивном вызове; если бы мы поступали таким образом, то время работы такого метода определялось бы рекуррентным соотношением Т(п) = = 2Т (и/2) + 0 (и 1к и), решение которого равно Т (и) = 0 (и 1бз п).
(Это можно показать с помощью версии основного метода, описанной в упражнении 4.4-2.) Немного позже станет понятно, как с помощью "предварительной сортировки" поддерживать отсортированность, не прибегая к процедуре сортировке в каждом рекурсивном вызове. В рекурсивном вызове со входными данными Р, Х и У сначала проверяется, выполняется ли условие ~Р~ < 3. Если оно справедливо, то в вызове просто применяется упомянутый выше метод решения "в лоб": сравниваются между собой все (~ з ~) пар точек, и возвращается пара точек, расположенных друг к другу ближе других. Если ~Р~ > 3, то производится рекурсивный вызов в соответствии с описанной ниже парадигмой "разделяй и властвуй".
Разделение. Находится вертикальная прямая 1, которая делит множество точек Р на два множества Рл и Рн, таких что ~Рт,Я = ЦР)/21, ~Рн~ = ЦР(/21', все точки множества Рл находятся слева от прямой 1 или на этой прямой, а все точки множества Ри находятся справа от прямой 1 или на этой прямой. Массив Х разбивается на массивы Хг. и Хи, содержащие точки множеств Рл и Рн соответственно, отсортированные в порядке монотонного возрастания координаты х. Аналогично, массив У разбивается на массивы Ул и Уи, содержащие соответственно точки множеств Рд и Ри, отсортированные в порядке монотонного возрастания координаты у.
Покорение. После разбиения множества Р на подмножества Рл и Рн производится два рекурсивных вызова: один для поиска пары ближайших точек в множестве Рл, а другой для поиска пары ближайших точек в множестве Рд. В качестве входных данных в первом вызове выступает подмножество Р~, и массивы Хг. и Уь1 во втором вызове на вход подается множество Рн, а также массивы Хи и Уд. Обозначим расстояния между ближайшими точками в множествах Рл и Ри через бь и дл соответственно; введем также обозначение б = ппп (бг„бн). Комбинирование. Ближайшая пара либо находится друг от друга на расстоянии б, найденном в одном из рекуррентных вызовов, либо образована точками, одна из которых принадлежит множеству Рг., а вторая — множеству Часть и'11.
Избранные темы 1076 ,-е. Рд )7 ° , '! е Р, к — — а --е+е-- о ---е) в 1 '..Рте ' е е ), Совпадающие точкиоаиав Р, одна в Р„ Совпаааюшие точкиоднав Р, одна в Рд а) б) Рд. В алгоритме определяется, существует ли пара таких точек, расстояние между которыми меньше б. Заметим, что если существует такая "пограничнаяе пара точек, расстояние между которыми меньше Б, то обе они не могут находиться дальше от прямой 1, чем на расстоянии б. Таким образом, как видно из рис.
33.11а, обе эти точки должны лежать в пределах вертикальной полосы шириной 2б, в центре которой находится прямая 1. Для поиска такой пары (если она существует) в алгоритме производятся описанные ниже действия. 1. Создается массив У' путем удаления из массива У всех точек, не попадающих в полосу шириной 2б.
Как и в массиве У, в массиве У' точки отсортированы в порядке возрастания координаты у. 2. Для каждой точки р из массива У' алгоритм пытается найти в этом же массиве точки, которые находятся в б-окрестности от точки р. Как мы вскоре увидим, достаточно рассмотреть лишь 7 точек, расположенных в массиве У' после точки р.
В алгоритме вычисляется расстояние от точки р до каждой из этих семи точек, и отслеживается, какое из расстояний от между всеми парами точек в массиве У' является наименьшим. 3. Если выполняется неравенство бт < б, то в вертикальной полосе действительно содержится пара точек, которые находятся друг от друга ближе, чем те, что были найдены в результате рекурсивных вызовов.
В этом случае возвращается эта пара точек и соответствующее ей расстояние й. В противном случае возвращается пара ближайших точек Рис. 33.11. Основные концепции, которые используются при доказательстве достаточно- сти проверки 7 точек массива У' при поиске пары ближайших точек Глава 33. Вычислительная геометрия 1077 и расстояние между ними б, найденное в результате рекурсивных вызовов. В приведенном выше описании опущены некоторые детали реализации, необходимые для сокращения времени работы до величины О (и 1я и).
После доказательства корректности алгоритма будет показано, как реализовать этот алгоритм так, чтобы достичь желаемой границы для времени работы. Корректность Корректность этого алгоритма, предназначенного для поиска пары ближайших точек, очевидна, за исключением двух аспектов. Во-первых, мы уверены, что в результате рекурсивного спуска до случая, когда ~Р~ < 3, никогда не придется решать вспомогательную задачу, в которой задана только одна точка. Второй аспект заключается в том, что понадобится проверить всего 7 точек, расположенных в массиве У' ниже каждой точки р; далее будет приведено доказательство этого свойства.
Предположим, что на некотором уровне рекурсии пару ближайших точек образуют точки рг. Е Рг, и ри Е Рл. Таким образом, расстояние б' между этими точками строго меньше б. Точка рг. должна находиться слева от прямой 1 на расстоянии, не превышающем величину б, или на этой прямой. Аналогично, точка рп находится справа от прямой 1 на расстоянии, не превышающем величину б, или на этой прямой. Кроме того, расстояние по вертикали между точками рг. и рл не превышает б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
