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

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

Файл №1162189 Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)) 237 страницаТ. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189) страница 2372019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

В этом случае эти два отрезка могут находиться в Т в любом порядке. Если всего имеется и входных отрезков, каждую из перечисленных выше операций с помощью красно-черных деревьев можно выполнить за время 0(1кп). Напомним, что операции над красно-черными деревьями, описанные в главе 13, включают в себя сравнение ключей.

Однако в нашем случае сравнение ключей Глава ЗЗ. Вычислительная геометрия !077 можно заменить векторным произведением, позволяющим определить относи- тельный порядок двух отрезков (см. упр. 33.2.2), Псевдокод, выявляющий пересечение отрезков В приведенном далее алгоритме в качестве входных данных выступает множество Я, состоящее из и отрезков. На выходе возвращается булево значение тКОЕ, если некоторая пара отрезюв из множества Я пересекается, и значение еАезе— в противном случае.

Полное упорядочение Т реализуется с помощью красно- черного дерева. Аху-Беомехтз-1хтекзест(Я) 1 Т= И 2 Сортировка юнечных точек отрезков э слева направо с разрешением совпадений путем помещения левых конечных точек перед правыми и путем помещения точек с меньшими координатами у перед теми, координата у которых больше 3 Гог каждой точки р в отсортированном списке конечных точек 4 1Гр является левой конечной точюй отрезка я 5 1хзект(Т,а) 6 1Г (Авоч7е(Т, л) существует и пересекает л) или (Вн.озг(Т, я) существует и пересекает з) 7 гетигп ткое 8 1Г р является правой конечной точкой отрезка л 9 1Г (и Авоуе(Т, я), и Вн.ощ(Т, я) существуют) и (Авоч7е(Т, я) пересекает Вн.о!у(Т, л)) !О гетпгп ТКУЕ 11 ьгЕСЕТЕ(Т,л) 12 гетпгп еАйзе Работа этого алгоритма проиллюстрирована на рис.33.5.

В строке 1 инициализируется пустое множество полностью упорядоченных отрезков. В строке 2 путем сортировки 2п конечных точек отрезюв слева направо создается таблица точек-событий с разрешением совпадений, как сказано выше. Одним из способов выполнения строки 2 является лексиюграфическая сортировка конечных точек (х, е, у), где х и у — обычные координаты, а переменная е принимает значение О для левых конечных точек и значение 1 — для правых конечных точек.

Каждая итерация цикла Гог в строках 3 — 11 обрабатывает одну точку-событие р. Если р является левой точкой отрезка е, то в строке 5 этот отрезок е добавляется в полностью упорядоченное множество, а в строках 6 и 7 возвращается значение тКОЕ, если отрезок л пересекает любой из отрезков, соседних с данным в полностью упорядоченном множестве, определяемом выметающей прямой, проходящей через р.

(Если точка р находится на другом отрезке з', имеет место граничный случай. При этом требуется лишь, чтобы отрезки л и е' были последовательными в множестве Т.) Если р представляет собой правую конечную точку отрезка я, то этот отрезок подлежит удалению из полностью упорядочен- гогг Часть 171 Избранные тены а а а И а' е Ь г а г и Ь г Ь г Ь Ь Время Рне.

33.5. Выполнение процедуры Амт-зяомнмтз-1мтндзнст. Каждая пункгнрная линия явллетея выметающей прямой, проводящей через одну нз точек-еобьпнй. За исключением крайней справа вымегающей линии упорядочение имен отрезков внизу под юпкдой выметающей линией соответствует полному упорядочению Т в конце цикла Гог, обрабатывающего соответствующую точку-еобытне. Крайняя справа выметающая прямая соответствует обработке правой конечной точки отрезка е; поеколъку отрезкн Ы н Ь окружают с н пересекают один другой, процедура возвращает тнщц ного множества. Но сначала, если пересекаются окружающие а отрезки из полностью упорядоченного множества, определенного выметающей прямой, которая проходит через точку р, в строках 9 и 10 возвращается значение ткие. Если зти отрезки не пересекаются, в строке 11 отрезок л удаляется из полностью упорядоченного множества.

Приведенное ниже доказательство корректности пояснит, почему достаточно проверки отрезков, окружающих л. Наконец, если во всех 2п точках-событиях не обнаружено никаких пересечений, в строке 12 возвращается значение РАезе. Корректность алгоритма Чтобы показать, что процедура А1чу-Бебментз-1хтеизест работает корректно, докажем, что при вызове Аму-Беоме1чтз-11чтекзест(Я) значение тк11е возвращается тогда и только тогда, когда какие-либо отрезки из Я пересекаются. Легко видеть, что процедура А1чу-Бепме1чтб-11чтейзест возвращает значение Тк11Е (в строках 7 и 10) толью в том случае, когда в ней обнаружено пересечение между двумя входными отрезками.

Таким образом, если возвращается значение ткие, то пересечение существует. Следует также показать обратное: если пересечение существует, то процедура А1чу-Беоме1чтз-1мтекзест возвращает значение тп11е. Предположим, что существует по крайней мере одно пересечение. Пусть р — крайняя слева точка пересечения (если таких точек несколько, то выбирается точка с наименьшей координатой у), а а и Ь вЂ” отрезки, пересекающиеся в этой точке. Поскольку слева от точки р нет никаких пересечений, порядок, заданный в множестве Т, остается правильным во всех точках, которые находятся слева от точки р.

Так как никакие три отрезка не пересекаются в одной и той же точке, существует выметающая 1073 Глава 33. Вычислпюптьюгн геомеюрия прямая г, относительно которой отрезки а и 6 расположены последовательно в полностью упорядоченном множестве . Более того, прямая г проходит через точку р или слева от нее. На выметаюшей прямой д находится конечная точка г) какого-нибудь отрезка, которая выступает в роли события, при котором отрезки а и 6 становятся последовательными в полностью упорядоченном множестве. Если на этой выметающей прямой лежит точка р, то г3 = р.

Если же точка р не принадлежит выметающей прямой г, то точка д находится слева от точки р. В любом случае порядок, установленный в множестве Т, является правильным непосредственно перед точкой д. (Вот где используется лексикографический порядок, в котором алторитм обрабатывает конечные точки. Поскольку р — самая низкая из крайних слева левых точек пересечения, то даже если она лежит на вымегающей прямой з и на этой прямой есть еше одна точка пересечения р', точка-событие г) = р обрабатывается перед тем, как эта другая точка пересечения сможет повлиять на порядок отрезков в упорядоченном множестве Т. Более того, даже если р — левая конечная точка одного отрезка (скажем, отрезка а) и правая конечная точка другого отрезка (скажем, отрезка Ь), то в силу того, что левые точки-события расположены перед правыми, отрезок 6 уже будет находиться в множестве Т, когда в это множество попадет отрезок а.) Каждая точка-событие г) ЛИбО ОбрабатЫВаЕтСя ПрОцЕдурОй АИУ-БЕПМЕХТЗ-1ЫТЕКЕЕСТ, ЛИбО Нст.

ЕСЛИ тОЧКа г) ОбрабатЫВаЕтСя ПрОцЕдурОй А!йу-БЕаМЕНТЗ-1НТЕКЗЕСТ, ВОЗ- можны всего два варианта выполняемых действий. !. Отрезок а либо отрезок Ь помещается в множество Т, и в этом множестве один из них расположен над нли под другим. То, какой из этих случаев имеет место, определяется в строках 4-7. 2. Отрезки а и 6 уже содержатся в множестве Т, а расположенный между ними отрезок удаляется из этого множества, в результате чего отрезки а и 6 становятся последовательными. Этот случай выявляется в строках 8-! !.

В любом случае мы находим пересечение р, и процедура А!чу-Бепментз1МТЕКЗЕСТ возвращает ТК!3Е. Если точка-событие г! не обрабатывается процедурой Аыу-Беоментз- 1!чтекзест, это означает, что произошел выход из процедуры до обработки всех точек-событий. Это может произойти только в том случае, если в этой процедуре уже была обнаружена точка пересечения и процедурой возвращено значение ТК!3Е. Таким образом, если отрезки пересекаются, то процедура Ану-Бегяьйемтз1нтекзест возвращает значение ткг3е. Как мы уже убедились, если процедура Аму-Бесменте-1нтекзест возвращает значение ткие, отрезки пересекаются. Поэтому рассматриваемая процедура всегда выдает правильный ответ. зЕсли позвоюпь трем отрезкам пересекаться в гжной точке, появитсв возможность сугпеспювания промежуточного стрелю с, пересекающею отрезки а и Ь в точке р.

Иначе говоря, для всех выметаюших прямых ю, расположенных слева от точки р, для «огорых а р Ь, могут выполняться иютношения а Ь с н с Ь Ь В упр. Зэд.й предлагается показать, что пропедура хит-Зпп мента-гмтипякСт работает корректно, даже если три отРезка пересекаются в олной и той же точке.

Часть р// //збраиные тЕны /014 Время работы Если множество Я содержит и отрезков, то процедура А/чт-Якомк/чтз- 1/чтпкзпст выполняется за время 0(п 1я п). Выполнение строки 1 занимает время 0(1). Строка 2 с помощью сортировки слиянием или пирамидальной сортировки выполняется за время 0(п !яп). Поскольку всего имеется 2п точек-событий, а цикл Гог в строках 3 — 1! выполняет не более одной итерации на точку, он выполняется не более 2п раз.

На каждую итерацию требуется время 0(1я п), поскольку выполнение каждой операции в красно-черном дереве занимает время 0(!йп), и с помощью метода, описанного в разделе 33.1, каждая проверка пересечения выполняется за время 0(1). Таким образом, полное время работы равно 0(п 1я и). Упражнения зз.гл Покажите, что в множестве, состоящем из п отрезков, может быть 9(пз) пересечений. ЗЗ.2.2 Пусть отрезки а и 6 сравнимы в координате а.

Покажите, как за время 0(1) определить, какое из соотношений выполняется — а >р 6 или 6 1ре а. Предполагается, что вертикальные отрезки отсутствуют. (Указание: если отрезки а и Ь не пересекаются, достаточно просто воспользоваться векторным произведением. Если же зти отрезки пересекаются, что выявляется путем вычисления векторных произведений, то и в этом случае можно ограничиться только операциями сложения, вычитания и умножения и избежать деления. Если отрезки а и 6 пересекаются, достаточно просто вывести сообщение о том, что обнаружено пересечение.) 33.2.3 Профессор предложил модифицировать процедуру А/чт-Бксмп/чтя-1//тккзпст таким образом, чтобы она не прекращала работу после того, как будет обнаружено пересечение, а выводила пересекающиеся отрезки и переходила к выполнению следующей итерации цикла Гог. Профессор назвал полученную в результате процедуру Рк//гт-1нтпкзпст//чс-Бкомк/чтя и заявил, что она выводит все пересечения, следующие слева направо в том порядке, в котором они располагаются в множестве отрезков.

Аспирант утверждает, что профессор ошибается. Кто из них прав? Всегда ли процедура Рк//чт-1мтпкзпст//ча-Бпсмп/чтз будет находить первым крайнее слева пересечение? Будет ли она находить все пересечения? 33.2.4 Разработайте алгоритм, позволяющий за время 0(п 1я п) определить, является лн и-угольник простым. 33.2.5 Разработайте алгоритм, позволяющий за время О(п1яп) определить, пересекаются ли два простых многоугольника, суммарное количество вершин в которых равно и.. 1075 Глаеа ЗЗ. Вычиееитееьиаи геометрии ЗЗ.г.б Круг состоит из окружности и ее внутренней области, и его можно представить с помощью центра и радиуса.

Два круга пересекаются, если у них есть хотя бы одна общяя точка. Приведите алгоритм, позволяющий в течение времени 0(п 1я и) определить, пересекаются ли какие-либо два круга из множества, состоящего из и кругов. 33.2. 7 Пусть задано множество, состоящее из и отрезков, между которыми имеется и пересечений. Покажите, как вывести данные по всем пересечениям за время ОЯп+ (е) 1яп). 33.2.8 Докажите, что процедура Аму-Бесмемтз-1мтедеест работает корректно даже в том случае, если в одной и той же точке пересекается три или более отрезков. 33.2.9 Покажите, что процедура А~г~-Бебмехтя-1хтедзест работает корректно даже в том случае, если в числе ее входных отрезков есть вертикальные (при этом нижние конечные точки вертикальных отрезков обрабатываются как левые конечные точки, а верхние — как правые юнечные точки).

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

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

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6510
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее