Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[268]

Задачи

813

правую половины можно за линейное время). Соответственно мы обязаны при рекурсивном вызове передавать множества Pl и Pr в отсортированном виде. Ясно, что это нетрудно сделать, проходя массив от начала к концу и раскладывая его элементы на две группы. В некотором смысле это действие обратно в процедуре Merge, использованной при сортировке слиянием (раздел 1.3.1).

Осталось заметить, что начальная сортировка (presorting) выполняется всего один раз и потому не входит в рекуррентное соотношение - её время нужно просто добавить к времени работы рекурсивной процедуры. Время этой сортировки есть О (га lgra), так что общее время есть сумма двух слагаемых вида О (га lgra) и потому есть О (га lgra).

Упражнения

35.4-1

Профессор предлагает усовершенствовать алгоритм поиска пары ближайших точек и проверять только 5 точек массива У. Он говорит следующее: «Будем относить точки, принадлежащие прямой /, к множеству Pr. В этом случае на прямой / не будет совпадающих точек, которые относятся одновременно к двум множествам Pl и Pr- Поэтому внутри прямоугольника 6x26 будет содержаться не более 6 точек.» Что неправильно в идее профессора?

35.4-2

Покажите, что (без изменения асимптотики времени работы алгоритма) можно подавать на вход алгоритма множество, не содержащее совпадающих точек. Покажите, что, если совпадающих точек в множестве нет, то для каждой точки массива У достаточно проверять 6 (а не 7) соседних точек. Объясните, почему нельзя обойтись 5 ближайшими точками.

35.4-3

Определим Ьт-расстояние (Lm-distance) между точками р\ и р2 плоскости формулой (ж! - Ж2т + 12/i - у2\т)1/т- Евклидово расстояние соответствует значению р = 2. Измените приведённый в этом разделе алгоритм так, чтобы он искал ближайшие точки в смысле Li-расстояния.

35.4-4

Определим Loo-расстояние между точками р\ и р2 как тах(ж! - ж21, г/1 - г/21) - Как приспособить алгоритм поиска ближайших точек к случаю Loo-расстояния?

35.5. Задачи

35-1 Выпуклые слои

Определим етрйвыпуклые слои (convex layers) множества Q точек плоскости. Первый выпуклый слой Q содержит точки множе-


ства Q, которые являются вершинами CH(Q). Выбросим эти эти точки и снова найдём выпуклую оболочку - её вершины образуют второй выпуклый слой. Выбросим и их; возьмём выпуклую оболочку остатка; её вершины образуют третий выпуклый слой и т.д.

a.Придумать способ за время 0(п2) найти все выпуклые слои множества из га точек плоскости.

b.Покажите, что задачу сортировки га вещественных чисел можно свести к задаче отыскания выпуклых слоев, и потому в любой модели, где сортировка требует времени \Omega(n\gn), та же оценка верна и для задачи отыскания выпуклых слоев.

35-2

Максимум-слои

Будем говорить, что точка плоскости (ж, у) мажорирует (dominates) точку (ж, у), если ж ж и у у. Пусть Q - множество точек плоскости. Если для точки из множества Q нет других точек из Q, мажорирующих её, то такую точку будем называть максимальной (maximal) в множестве Q. Таких точек может быть несколько; множество таких точек называют первым максимум-слоем. Удалив все эти точки, повторим процесс с оставшимся множеством точек, получим второй максимум-слой, и будет это повторять до тех пор, пока точки не кончатся.

Предположим, что множество Q имеет к непустых максимум слоев L\, L2, , Lk- Пусть уг- - ордината самой левой точки слоя Li для г = 1,2,...к. Будем предполагать, что в Q нет двух точек с совпадающими абсциссами или ординатами.

a.Докажите, что у\ > у2 > ... > Ук-

Пусть точка (ж, у) находится левее любой из точек Q, а её ордината у отлична от ординат всех точек множества Q. Пусть

д = ди{(ж,у)}.

b.Обозначим через j наименьший из индексов, для которых yj < у; если такого индекса нет (у < ук), положим j = к + 1. Покажите, что максимум-слои множества Ql устроены так:

Если j к, то все максимум-слои Q совпадают с максимум-слоями Q, за исключением слоя Lj, в который добавилась точка (ж, у) (и стала самой левой точкой нового Lj).

Если j = к + 1, то первые к максимум-слоев множества Q такие же, как у Q, но кроме них есть непустой (& + 1)-ый слой, состоящей из единственной точки (ж, у).

c.Опишите алгоритм, вычисляющий все максимум-слои множества из п точек за время О (га lgra). (Указание. Двигайте прямую справа налево.)

d.Какие сложности возникнут, если среди точек есть точки с равными абсциссами или ординатами, и как можно поступить в таком случае?

35-3 Роботы и призраки.

Команда из га роботов сражается с га призраками. Каждый робот


Задачи

815

вооружён протонным ружьём, луч которого уничтожает призрак. Луч движется по прямой и обрывается, встретив призрак. Тактика роботов такова: каждый выбирает себе призрак (при этом образуется га пар робот - призрак), а затем все роботы одновременно выпускают лучи каждый в свое приведение. При этом нельзя, чтобы выпускаемые роботами лучи пересеклись.

Считаем, что положение каждого робота и каждого призрака - заданная точка плоскости, и никакие три из этих точек не лежат на одной прямой.

a.Доказать, что всегда существует прямая, соединяющая одного из роботов с одним из призраков, для которой число роботов по одну сторону от неё совпадает с числом призраков с той же стороны. Придумайте, как найти такую прямую за время О (га lgra).

b.Постройте алгоритм, за время О (га2 lg га) группирующий роботов и приведений в пары так, чтобы выпускаемые роботами лучи не пересекались.

35-4. Распределение с малой оболочкой.

Пусть мы хотим построить выпуклую оболочку множества случайных точек плоскости, подчиняющихся некоторому распределению вероятностей (различные точки независимы). Для некоторых распределений математическое ожидание числа вершин выпуклой оболочки есть 0(га1 е) для некоторой константы е > 0 (здесь га - число точек). Такие распределения мы будем называть распределениями с малой оболочкой (sparse-hulled distributions). Вот примеры таких распределений:

Точки равномерно распределены внутри круга единичного радиуса. Выпуклая оболочка имеет в среднем 0(га1/,э) вершин.

Точки равномерно распределены внутри фиксированного выпуклого многоугольника. Выпуклая оболочка содержит в среднем O(lgra) вершин. (Константа зависит от числа вершин многоугольника.)

Точки подчинены двумерному нормальному распределению. Выпуклая оболочка содержит в среднем Q(\/lg га) вершин.

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

b.Постройте алгоритм, который отыскивает выпуклую оболочку га независимых точек, подчинённых некоторому распределению с малой оболочкой. Математическое ожидание времени работы т алгоритма должно быть О (га). (Указание. Рекурсивно ищем выпуклую оболочку для двух половин множества, а затем соединяем эти выпуклые оболочки в одну.)

Замечания

В этой главе мы лишь слегка коснулись задач вычислительной геометрии. Книги по вычислительной геометрии написали Препа-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]