Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 242

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 242)

1091 Глава 33. Вычаюительяая геачетрия Упражнения 33.4.1 Профессор предложил схему, позволяющую ограничиться в алгоритме поиска пары ближайших точек пятью точками, которые находятся в массиве У' после каждой из точек. Его идея заключается в том, чтобы точки, которые лежат на прямой 1, всегда заносились в множество Ре, Тогда на этой прямой не может быть пар совпадающих точек, одна из которых принадлежит множеству Ре., а другая— множеству Рн. Таким образом, прямоугольник размером Ю х 2б может содержать не более шести точек. Какая ошибка содержится в предложенной профессором схеме? 33.4.2 Покажите, что в действительности достаточно проверки точек только в пяти по- зициях массива, следующих за каждой точкой в массиве У'.

33.4.3 Расстояние между двумя точками можно определить и не в евклидовом смысле, а по-другому. Так, йеа-ревсстоянне (Ь ийззапсе) между точками р1 и рз на плоскости задается выражением ((к1 — хз~ + (рз — уз) )'1 . Таким образом, евклидово расстояние — это Ьз-расстояние. Модифицируйте алгоритм поиска пары ближайших точек для Ьз-расстояния, известного как маихэшвяенское рассшоялие (Маплапап яйзгапсе).

33.4.4 Для двух точек, рз и рз, заданных на плоскости, Л -расстоянием между ними называется величина шах((хз — хз), (у1 — узо. Модифицируйте алгоритм поиска пары ближайших точек для Ь -расстояния. 33.4.5 Предположим, что среди переданных алгоритму поиска пар ближайших точек имеется П(п) ковертикальных. Покажите, как определить множества Ре, и Рл и как определить, находится ли каждая точка У в Рь или Рл так, чтобы время работы алгоритма осталось равным 0(п 1К и). 33.4.6 Предложите, как изменить алгоритм поиска пары ближайших точек, чтобы избежать в нем предварительной сортировки массива У, но чтобы время его работы по-прежнему оставалось равным 0(п )к п). (Указание: объедините отсортированные массивы У1, и Ун в отсортированный массив У.) 1092 Часть ре.

Избранные тены Задачи 33.1. Выпуклые слон Для заданного на плоскости множества точек Я выпуклые слои (сопчех !ауегз) определяются следующим индуктивным образом. Первый выпуклый слой множества Я состоит из вершин СН(Я). Определим для 1 > 1 множество Яо состоящее из точек множества Я, из которого удалили все точки выпуклых слоев 1, 2,..., з — 1. Тогда з-м выпуклым слоем множества Я является СН(Я,), если 1„!з Ф 9; в противном случае он считается неопределенным. а Разработайте алгоритм, который находил бы выпуклые слои множества иэ и точек за время 0(пг). 6.

Докажите, что для построения выпуклых слоев в множестве из п точек по любой вычислительной модели, в которой сортировка п действительных чисел занимает время П(п !к п), требуется время П(п 1к и). 33.2. Максимальные слои Пусть 1;! — множество п точек на плоскости. Говорят, что точка (х, у) даминирует (бош)пагез) над точкой (х',у'), если выполняются неравенства х > х' и у > у'.

Точка множества Я, над которой не доминирует никакая другая точка этого множества, называется макснмааьной (шахппа1). Заметим, что множество Я может содержать большое количество максимальных точек, которые можно объединить в максимальные слон (шахппа1 1ауегз) следующим образом. Первый максимальный слой 1,| представляет собой множество максимальных точек множества Я. Для 1 > 1 определим 1-й максимальный слой Ц как множество максимальных точек в Я вЂ” Ц:, Ез.

Предположим, что множество Я содержит к непустых максимальных слоев, и пусть у, — координата у крайней слева точки в слое Тл (з = 1,2,..., )с), Мы предполагаем, что координаты х или у никаких двух точек множества Я не совпадают. ьь Покажите, что у1 > уг » уь Рассмотрим точку (х, у), которая находится левее всех точек множества ь1 и координата у которой отличается от координаты у любой другой точки этого множества. Введем обозначение Я' = Я О ((х, у)). б.

Пусть г — минимальный индекс, такой что у < у; если такого индекса нет (у < уь), то г' = /с + 1. Покажите, что максимальные слои множества Я' обладают следующими свойствами. Если 9 < lс, то максимальные слои множества Я' совпадают с максимальными слоями множества Я, за исключением слоя Ьз, который в качестве новой крайней слева точки включает точку (х, у). 10Р3 Глава 33. Вычислительипа геометрии Если 3' = й + 1, то первые )с максимальных слоев множества Я' совпадают с максимальными слоями множества (4', но, кроме того, множество (4' имеет непустой ()с + 1)-й максимальный слой Ь)сь) = 1(а, у)).

ж Разработайте алгоритм, позволяющий за время 0(п1йн) построить максимальные слои множества (4, состоящего из и точек. (Укозаниег проведите вертикальную выметаюшую прямую справа налево.) л Возникнут ли какие-либо сложности, если разрешить входным точкам иметь одинаковые координаты к или у? Предложите способ решения таких проблем. 33.3. Привидения и охознники за ними Группа, состоящая из п охотников за привидениями, борется с п привидениями. Каждый охотник вооружен протонной установкой, уничтожающей привидение протонным пучком. Поток протонов распространяется по прямой и прекращает свой путь, когда попадает в привидение. Охотники придерживаются следующей стратегии.

Каждый из них выбирает среди привидений свою цель, в результате чего образуется п пар "охотник-привидение". После этого каждый охотник выпускает пучок протонов по своей жертве. Известно, что пересечение пучков очень опасно, поэтому охотники должны выбирать привидения так, чтобы избежать таких пересечений. Предположим, что положение каждого охотника и каждого привидения задано фиксированной точкой на плоскости и что никакие три точки не коллинеарны. а Докажите, что всегда существует прямая, проходящая через одного охотника и одно привидение, для которой количество охотников, попавших в одну из полуплоскостей относительно этой прямой, равно количеству привидений в этой же полуплоскости. Опишите, как найти такую прямую за время 0(п 1к и).

6. Разработайте алгоритм, позволяющий в течение времени 0(па 1кп) разбить охотников и привидения на пары таким образом, чтобы не было пересечения пучков. 33.4. Сбор палочек Профессор занимается исследованием множества из п палочек, сложенных в кучу в некоторой конфигурации. Положение каждой палочки задается ее конечными точками, а кал(дая конечная точка представляет собой упорядоченную тройку координат (я, у, з). Вертикальных палочек нет.

Профессор хочет собрать по одной все палочки, соблюдая условие, согласно которому он может снимать палочку только тогда, когда поверх нее не лежат никакие другие палочки. зв оригинале — непереводимаз игра слов профессор Харон и палочки (зггсйз). Харон в греческой мифологии — перевозчик луш умерших через реку Стикс в Аид (подземное парство мертвык). — Примеч.

иер. !094 Часть Г72 Иэбранные тсмн я. Разработайте процедуру, которая для двух заданных палочек, а и Ь, определяла бы, находится ли палочка а над палочкой Ь, под ней или палочка а не связана с палочкой Ь ни одним из этих соотношений. б. Разработайте эффективный алгоритм, позволяющий определить, можно ли собрать все палочки, и в случае положительного ответа предлагаюший допустимую последовательность, в которой нужно собирать палочки.

33.5. Разренсенно-оболочечные распределения Рассмотрим задачу вычисления выпуклой оболочки множества заданных на плоскости точек, нанесенных в соответствии с каким-то известным случайным распределением. Для некоторых распределений математическое ожидание размера (количества точек) выпуклой оболочки такого множества, состоящего из п точек, равно 0(п1 '), где с > 0 — некоторая положительная константа. Назовем такое распределение разренсенно-оболочечным (зрагзе-Ъп11еб). К разрежен- но-оболочечным распределениям относятся следующие.

Точки, равномерно распределенные в круге единичного радиуса. Ожидаемый размер выпуклой оболочки равен 9(п'7з). Точки, равномерно распределенные внутри выпуклого й-угольника, где )г — произвольная константа. Ожидаемый размер выпуклой оболочки равен ~(18 п) Точки наносятся в соответствии с двумерным нормальным распределением. Ожидаемый размер выпуклой оболочки равен гЭ(~(18 и).

а Даны два выпуклых многоугольника с п1 и из вершинами соответственно. Покажите, как построить выпуклую оболочку всех п1 + пз точек за время 0(п1 + из). (Многоугольники могут перекрываться.) б. Покажите, как вычислить выпуклую оболочку и независимых точек, подчиненных некоторому разреженно-оболочечному распределению, за время 0(п).

(Указание: рекурсивно постройте выпуклую оболочку для двух половин множества, а затем объедините полученные результаты.) Заключительные замечания В этой главе мы лишь вкратце обсудили тему алгоритмов и методов вычислительной геометрии. Среди серьезных изданий по вычислительной геометрии можно выделить книги Препараты (Ргерагага) и Шамоса (БЪашоз) [280), а также Эдельсбруннера (Еде!зЪпшпег) [98) и О'Рурка (О'Копгке) [267). Несмотря на то что геометрия изучается с античных времен, развитие алгоритмов для геометрических задач — относительно новое направление.

Характеристики

Список файлов книги