Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 222
Текст из файла (страница 222)
Таким образом, как видно из рис. 33.11а, точки рг. и рл находятся внутри прямоугольника б х 2б, через центр которого проходит прямая 1. (В этот прямоугольник могут также попасть другие точки.) Теперь покажем, что прямоугольник размерами б х 2б может содержать не более восьми точек. Рассмотрим квадрат б х б, который составляет левую половину этого прямоугольника. Поскольку расстояние между любой парой точек из множества Рл не меньше б, в этом квадрате может находиться не более четырех точек (рис. 33.11б).
Аналогично, в квадрате размерами б х б, составляющем правую половину означенного прямоугольника, тоже может быть не более четырех точек. Таким образом, в прямоугольнике б х 2б содержится не более восьми точек. (Заметим, что поскольку точки на прямой 1 могут входить либо в множество Рд, либо в множество Рл, на этой прямой может лежать до четырех точек. Этот предел достигается, если имеется две пары совпадающих точек, причем в каждой паре одна из точек принадлежит множеству Рь, а другая — множеству Рл. Кроме того, одна из этих пар находится на пересечении прямой 1 и верхней стороны прямоугольника, а вторая — на пересечении прямой 1 и нижней стороны прямоугольника.) Поскольку в прямоугольнике указанных выше размеров может содержаться не более восьми точек множества Р, очевидно, что достаточно проверить 7 точек, Часть Чй.
Избранные темы 1078 расположенных в массиве У' после каждой точки. Продолжая придерживаться предположения, что пара ближайших друг к другу точек состоит из точек рь и рл, без потери общности предположим, что в массиве У' точка рь находится перед точкой рл. В этом случае точка рн является одной из семи точек, следующих после точки рг,, даже если точка рь встречается в массиве У' так рано, насколько это возможно, а точка рн — настолько поздно, насколько это возможно. Таким образом, корректность алгоритма, предназначенного для поиска пары ближайших точек, доказана. Реализация и время работы алгоритма Как уже упоминалось, наша цель заключается в том, чтобы показать, что время работы представленного алгоритма описывается рекуррентным соотношением Т (и) = 2Т (п/2) + О (и), где Т (и) — время работы алгоритма для и точек. Основная сложность — это добиться, чтобы массивы Хь, Хд, Уь н Ун, которые передаются в рекурсивных вызовах, были отсортнрованы по соответствующей координате и чтобы массив У' был отсортировал по координате у.
(Заметим, что если массив Х, который передается в рекурсивном вызове, уже отсортировал, то разбиение множества Р на подмножества Рь и Рн легко выполнить в течение времени, линейного по количеству элементов.) Главное заключается в том, что в каждом вызове следует сформировать отсортированное подмножество отсортированного массива. Например, пусть в какомто отдельно взятом рекурсивном вызове задано подмножество Р и массив У, отсортированный по координате у. В процессе разбиения множества Р на подмножества Рь и Рл нужно образовать массивы Уь и Ун, которые должны быть отсортированы по координате у. Более того, эти массивы необходимо сформировать в течение линейного времени. Этот метод можно рассматривать как антипод процедуры Миксе, описанной в разделе 2.3.1: отсортированный массив разбивается на два отсортированных массива.
Эта идея реализована в приведенном ниже псевдокоде. 1 1епдй[Уь] +- 1епдй[Ун] — 0 2 1ог г' — 1 Фо 1епдй[У] 3 йо и У[1] е Рг, 4 1йеп 1епдй[Уь] ~ — 1епдй[Ул] + 1 5 Уь[1епдй[Щ У[т] 6 е1ве 1епдй[Ул] - 1елдй[Ул] + 1 7 Ул[1епдй[Ун]] У[1] Точки массива У просто обрабатываются в порядке их расположения в этом массиве.
Если точка У [1] принадлежит множеству Рс, она добавляется в конец массива Глава 33. Вычислительная геометрия 1079 Уг.; в противном случае она добавляется в конец массива Ул. С помощью аналогичного псевдокода можно сформировать массивы Хг., Хл и У'. Единственный оставшийся вопрос — как сделать так, чтобы точки были отсортированы с самого начала. Для этого следует провести их нредварнтелъную сортировку (ргезоп1пя); т.е. это делается один раз леред первым рекурсивным вызовом. Отсортированные массивы передаются в первом рекурсивном вызове, а затем они будут дробиться в рекурсивных вызовах до тех пор, пока это будет необходимо. Предварительная сортировка добавит ко времени работы алгоритма величину О (и !к и), но позволит выполнять каждый шаг рекурсии в течение линейного времени.
Таким образом, если обозначить через Т(и) время обработки каждого шага рекурсии, а через Т' (и) — общее время работы всего алгоритма, то получим равенство Т' (и) = Т (и) + О (и !к и) и соотношение (2Т (и/2) + О (и) если и > 3, Т(и) = (О (1) если и < 3. Таким образом, Т (и) = О (и 1ки) и Т (и) = О (и !к и). Упражнения 33.4-1. Профессор предложил схему, позволяющую ограничиться в алгоритме поиска пары ближайших точек пятью точками, которые находятся в массиве У' после каждой из точек.
Его идея заключается в том, чтобы точки, которые лежат на прямой 1, всегда заносились в множество Рь. Тогда на этой прямой не может быть пар совпадающих точек, одна из которых принадлежит множеству Р~„а другая — множеству Рл. Таким образом, прямоугольник размерами б х 2б может содержать не более шести точек. Какая ошибка содержится в предложенной профессором схеме? 33.4-2. Покажите, как без ухудшения асимптотичесюго времени работы алгоритма убедиться в том, что передаваемое в самом первом рекурсивном вызове множество не содержит совпадающих точек. Докажите, что в этом случае достаточно проверять по 5 точек, расположенных после каждой точки в массиве У'. 33.4-3. Расстояние между двумя точками можно определить и не в евклидовом смысле, а по-другому.
Так, ),„-расстояние (Ьы-б!з!апсе) между точками р1 и рз на плосюсти задается выражением Ох1 — хз) + )у1 — уз)™) Поэтому евклидово расстояние — это Ьз-расстояние. Модифицируйте алгоритм поиска пары ближайших точек для Ь|-расстояния, известного как манхэттенское расстояние (Мап!запал йз!апсе). Часть ЧП. Избранные темы 1080 33.4-4. Для точек рг и рз, заданных на плоскости, Ь -расстоянием между ни- ми называется величина шах ((хг — хз), )уг — уз~). Модифицируйте ал- горитм поиска пары ближайших точек для Ь -расстояния. 33.4-5. Предложите, как изменить алгоритм поиска пары ближайших точек, что- бы избежать в нем предварительной сортировки массива У, но чтобы время его работы по-прежнему осталось равным О (п1яп). (Указание: объедините отсортированные массивы Уг. и Ул в отсортированный массив У.) Задачи 33-1.
Выпуклые слои Для заданного на плоскости множества точек Я вынунлме слои (соптех 1ауегз) определяются следующим образом. Первый выпуклый слой множества Я состоит из вершин СН (Я). Уберем эти точки и снова найдем выпуклую оболочку — ее вершины образуют второй выпуклый слой. Отбросим их и возьмем выпуклую оболочку остатка — ее вершины образуют третий выпуклый слой и т.д. Строго выпуклые слои определяются инлуктивно следующим образом. Первый выпуклый слой множества (~ состоит из вершин СН Я). Определим при 1 > 1 множество Я;, состоящее из точек множества Я, из которого удалили все точки выпуклых слоев 1, 2,..., г — 1.
Тогда г-м выпуклым слоем множества Я является СН ©), если Я; ,-4 9; в противном случае он считается неопределенным. а) Разработайте алгоритм, который находил бы выпуклые слои множества из и точек в течение времени О (пз). б) Докажите, что для построения выпуклых слоев в множестве из и точек по любой вычислительной модели, в которой сортировка п действительных чисел занимает время Й(п1кп), требуется время Й(п1бп).
33-2. Максимальные слои Пусть Я вЂ” множество п точек на плоскости. Говорят, что точка (х, у) доминируегн (бош1па1ез) над точкой (х', у'), если выполняются неравенства х > х' и у > у'. Точка множества Я, над которой не доминирует никакая другая точка этого множества, называется максимальной (гпахппа1). Заметим, что множество Я может содержать большое количество максимальных точек, которые можно объединить в максимальные слои (шахппа1 1ауегз) следующим образом. В первый максимальный слой Ьг образует подмножество максимальных точек множества Я.
При г > 1 Глава 33. Вычислительная геометрия 1081 1-м максимальным слоем Е; является подмножество максимальных точек множества Я вЂ” Ц з'з. Предположим, что множество Я содержит 1с непустых максимальных слоев, и пусть у; — координата у самой левой точки в слое Ц (1 = = 1,2,..., )с). Мы предполагаем, что координаты х или у никаких двух точек множества Я не совпадают. а) Покажите, что уз > уз » .
уь. Рассмотрим точку (х, у), которая находится левее всех точек множества Я и координата у которой отличается от координаты у любой другой точки этого множества. Введем обозначение Я' = Я 0 1(х, у)). б) Пусть з — минимальный индекс, такой что у < у; если такого индекса нет (у < уь), то з = 1с+ 1. Покажите, что максимальные слои множества Я' обладают следующими свойствами. ° Если з < )г, то максимальные слои множества Я' совпадают с максимальными слоями множества Я за исключением слоя Ц, который в качестве новой крайней левой точки включает точку (х, у).
° Если з = к + 1, то первые )с максимальных слоя множества Я' совпадают с максимальными слоями множества ф но, кроме того, множество Я' имеет непустой (1+1)-й максимальный слой Ьь+~ = ((х,у)). в) Разработайте алгоритм, позволяющий в течение времени О (и 18 и) построить максимальные слои множества Я, состоящего из и точек. (Указание: проведите вертикальную выметающую прямую справа налево.) г) Возникнут ли какие-либо сложности, если разрешить входным точкам иметь одинаковые координаты х или у? Предложите способ решения таких проблем.
33-3. Охотники за привидениями и привидения Группа, состоящая из и охотников за привидениями, борется с и привидениями. Каждый охотник вооружен протонной установкой, уничтожающей привидение протонным пучком. Поток протонов распространяется по прямой и прекращает свой путь, когда попадает в привидение. Охотники придерживаются такой стратегии. Каждый из них выбирает среди привидений свою цель, в результате чего образуется и пар "охотник-привидение". После этого каждый охотник выпускает пучок протонов по своей жертве. Известно„что пересечение пучков очень опасно, поэтому охотники должны выбирать привидения так, чтобы избежать пересечений. 1082 Часть Ч11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
