Алгоритмы - построение и анализ (1021735), страница 219
Текст из файла (страница 219)
Это может произойти только в том случае, когда в этой процедуре уже была обнаружена точка пересечения и процедурой возвращено значение тле. Таким образом, если отрезки пересекаются, то процедура Ам' Яваиннтз 1нтккзкст возвращает значение тле. Как мы уже убедились, если процедура Ану Беамннтз 1нтникст возвращает значение тадж, отрезки пересекаются. Поэтому рассматриваемая процедура всегда выдает правильный ответ.
Время работы Если в множестве Я содержится и отрезков, то процедура Аму БеОментз 1нтепзпст выполняется в течение времени 0 (и 1я и). Выполнение строки 1 занимает время О (1). Строка 2 с помощью сортировки слиянием или пирамидальной сортировки выполняется в течение времени 0 (п1яп). Поскольку всего имеется 2п точек-событий, цикл 1ог в строках 3-11 повторяется не более 2п раз. На каждую итерацию требуется время 0 (18 п), поскольку выполнение каждой операции в красно-черном дереве занимает время О (1к и), и с помощью метода, описанного Часть Ч1!. Избранные темы 1062 Упражнения 33.2-1.
Покажите, что в множестве, состоящем из п отрезков, может быть О (пз) пересечений. 33.2-2. Пусть отрезки а и Ь сравнимы в координате х. Покажите, как за время 0 (1) определить, какое из соотношений выполняется — а > Ь или Ь > а. Предполагается, что вертикальные отрезки отсутствуют. (Указание: если отрезки а и Ь не пересекаются, достаточно просто воспользоваться векторным произведением. Если же эти отрезки пересекаются, что выявляется путем вычисления векторных произведений, то и в этом случае можно ограничиться только операциями сложения, вычитания и умножения, и избежать деления. Если отрезки а и Ь пересекаются, достаточно просто вывести сообщение, что обнаружено пересечение.) 33.2-3. Профессор предложил модифицировать процедуру Ан~' Бнпмечтз 1нтннзнСт таким образом, чтобы она не прекращала работу после того, как будет обнаружено пересечение, а выводила пересекающиеся отрезки и переходила к выполнению следующей итерации цикла 1ог.
Профессор назвал получившуюся в результате процедуру Рнп й' 1нтнкзнстпчс Бнамннтз и заявил, что она выводит все пересечения, следующие слева направо в том порядке, в котором они располагаются в множестве от- резков. Покажите, что профессор ошибается в двух аспектах. Для этого приведите пример множества отрезков, для которых первая точка пере- сечения, обнаруженная процедурой Рипа 1нтнкзнстпчо Бнпмннтз, не является самой левой, а также пример множества отрезков, для которых эта процедура выявляет не все пересечения. Разработайте алгоритм, позволяющий в течение времени 0 (и 1я п) опре- 33.2-4.
делить, является ли и-угольник простым. Разработайте алгоритм, позволяющий в течение времени 0 (и 1к и) опре- 33.2-5. делить, пересекаются ли два простых многоугольника, суммарное коли- чество вершин в которых равно п. Круг (<Ыс) состоит из окружности и ее внутренней области, и его можно представить при помощи центра и радиуса. Два круга пересекаются, если у них есть хоть одна общая точка. Приведите алгоритм, позволяющий в течение времени О (п1кп) определить, пересекаются ли какие-либо два круга из множества, состоящего из п кругов.
33.2-6. в разделе 33.1, каждый тест на пересечение удается выполнить за время 0 (1). Таким образом, полное время равно О (п 1к и). Глава 33. Вычислительная геометрия 1063 33.2-7. Пусть задано множество, состоящее из п отрезков, между которыми имеется й пересечений. Покажите, как вывести данные по всем пересечениям в течение времени О Ип + lс) 18 п). 33.2-8. Покажите, что процедура Аыу Бепмехтз 1хтеизест работает корректно даже в том случае, если в одной и той же точке пересекается три или больше отрезков. 33.2-9. Покажите, что процедура Ам" БЕамннтз 1итнинст работает корректно даже в том случае, если в числе ее входных отрезков есть вертикальные. При этом нижние конечные точки вертикальных отрезков обрабатываются как левые конечные точки, а верхние — как правые конечные точки.
Как изменится ответ в упражнении 33.2-2, если допускается наличие вертикальных отрезков? 33.3 Построение выпуклой оболочки Выпуклой оболочкой (сопкех 1ш1!) множества точек Я называется наименьший выпуклый многоугольник Р, такой что каждая точка из Я находится либо на границе многоугольника Р, либо в его внутренней области. (Точное определение выпуклого многоугольника можно найти в упражнении 33.1-5.) Обозначим выпуклую оболочку множества Я как СН Я). Интуитивно можно представлять каждую точку множества ц в виде торчащего из доски гвоздя; тогда выпуклая оболочка будет иметь форму, полученную в результате наматывания на гвозди тугой резиновой нити.
Пример множества точек и их выпуклой оболочки приведен на рис. 33.6. В этом разделе представлены два алгоритма, позволяющие построить выпуклую оболочку множества, состоящего из п точек. Оба алгоритма выводят верши- Рз Рп Рнс. 33.6. Множество точек Я = (ро, рп..., р1з) и нх выпуклая оболочка СН Я) 1064 Часть Ч!!. Избранные темы ны выпуклой оболочки в порядке обхода против часовой стрелки.
Время работы первого из них, известного как сканирование по Грэхему, равно 0 (и !яп). Второй алгоритм, который называется обходом по Джарвису, выполняется в течение времени О (пЬ), где Ь вЂ” юличество вершин выпуклой оболочки. Как видно из рис. 33.6, каждая вершина СН(Я) — это точка из множества Я. Это свойство используется в обоих алгоритмах. В них принимается решение, какие точки из множества Я выступают в роли вершин выпуклой оболочки, а какие следует отбросить. Фактически имеется несюлью методов построения выпуклой оболочки в течение времени О (и !кп). И при сканировании по Грэхему, и при обходе по Джарвису используется метод, который называется "выметанием по кругу".
Вершины обрабатываются в порядке возрастания их полярных углов, которые они образуют с некоторой базисной вершиной. В число других методов входят те, что перечислены ниже. ° В методе лосявдсвательного счета (! псгешеп!л! шегйод) точки сортируются слева направо, в результате чего получается последовательность (ры рз, ..., р„). На г-м этапе выпуклая оболочка г — 1 самых левых точек СН((ры рз, ...,р; 1)) обновляется в соответствии с положением г'-й слева точки, после чего формируется оболочка СН ((ры рз,..., р!)).
В упражнении 33.3-6 предлагается показать, что этот метод можно реализовать так, чтобы время его работы было равно 0 (и 1к и). ° В методе двквмлозиции (дечЫе-апд-солцне ше!йод) множество и точек за время 0 (и) разбивается на два подмножества, в одном из которых содержится !и/21 самых левых точек, а во втором — 1и/2!' самых правых точек. Затем рекурсивно строятся выпуклые оболочки этих подмножеств, которые затем объединяются с помощью одного остроумного метода в течение времени О (и). Время работы этого метода описывается уже знакомым рекуррентным соотношением Т(п) = 2Т(п/2) + 0(п), решение которого равно 0(п1кп). ° Метод отсечения и лолска (рпше-алб-зеагсЬ ше!йод) подобен алгоритму, описанному в разделе 9.3, время работы юторого в наихудшем случае ведет себя линейно.
В нем строится верхняя часть (или "верхняя цепь") выпуклой оболочки путем повторного отбрасывания фиксированной части оставшихся точек до тех пор, пока не останется толью верхняя цепь выпуклой оболочки. Затем то же самое выполняется с нижней цепью. В асимптотическом пределе этот метод самый быстрый: если выпуклая оболочка содержит Ь вершин, время его работы равно О (и!к Ь). Построение выпуклой оболочки множества точек — задача, интересная сама по себе. Кроме того, алгоритмы, предназначенные для решения неюторых других Глава 33.
Вычислительная геометрия 1065 задач вычислительной геометрии, начинают работу с построения выпуклой оболочки. Например, рассмотрим двумерную задачу о поиске пары самых дальних точек (Тагг)зезг-ра)г ргоЫеш): в заданном на плоскости множестве и точек требуется найти две, расстояние между которыми является максимальным. В упражнении 33.3-3 предлагается доказать, что обе эти точки должны быть вершинами выпуклой оболочки. Пару самых дальних вершин выпуклого и-угольника можно найти в течение времени 0 (и), хотя здесь мы не станем доказывать это утверждение. Таким образом, путем построения выпуклой оболочки и входных точек за время 0 (и 1я и) и последующего поиска пары самых дальних точек среди вершин полученного в результате выпуклого многоугольника, можно найти пару самых дальних точек из произвольного множества и точек за время 0 (и 1я и). Сканирование по Грэхему В методе сканирования по Грэхему (Огалаш'з зсап) задача о выпуклой оболочке решается с помощью стека Я, сформированного из точек-кандидатов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
