Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рис. 4.23. Конструкция множества из N точек в трехмерном пространстве с числом противолежащих пар, равным 0{№).
и 0(N2) соответственно. В самом деле, не составляет труда конструктивно продемонстрировать тот факт, что число противолежащих пар в трехмерном пространстве может расти как 0(N2). Соответствующий пример приведен на рис. 4.23, где нужная конфигурация получается в результате замены двух несмежных ребер тетраэдра двумя «цепями» по N/2 вершин в каждой. Любая пара вершин — по одной вершине из каждой цепи — образует противолежащую пару. Таким образом, процедура поро-
4.4. Упражнения
225
Яо [Yao (1982)] предложил несколько иной подход к задаче вычисления диаметра множества. Этот подход позволил получить алгоритм со сложностью о(№). А именно оценка времени работы алгоритма равна
Т (N, d) = 0 (Nz~a (d) (log N)1 ~a
где a(d) = 2~(-d+}\ Для d — 3 эту оценку можно улучшить до О ((N log N) '¦8). Вопрос о том, можно ли уменьшить различие между Т (N, d) и Q(A4ogA/), остается открытым.
4.4. Упражнения
1. Пусть 5 —множество из N точек на плоскости. Обе координаты каждой точки являются целыми числами, не превосходящими m (точки, заданные на решетке). Разработать алгоритм построения выпуклой оболочки CH(S) со временем обработки 0(N + m).
2. Пусть S — множество из Л' = т2 точек в Е3, определенное следующим образом:
S = {Рц: х = i, у {Р{1) = /, г > 0, 0 < /, / < т).
Разработать специальный алгоритм построения верхней оболочки множества S.
3. Проверка на максимум в Е2. На плоскости задано множество 5 из N точек. Разработать метод, проверяющий за время O(logiV), является ли некоторая точка q максимумом множества SUM- (Предполагается режим многократных запросов — см. разд. 2.1.) Время, затрачиваемое на создание структуры данных, используемой для поиска, не должно превышать 0(N\ogN), а занимаемый ею объем памяти — О(N).
4. Проверка на максимум в Е3. В пространстве Е3 задано множество 5 из N точек. Разработать метод, проверяющий за время O(logW), является ли некоторая точка q максимумом множества S|J{<7}- (Предполагается режим многократных запросов.) Время, затрачиваемое на создание структуры данных, используемой для поиска, не должно превышать 0(N\ogN), а занимаемый ею объем памяти — О (N). (Указание: использовать метод локализации точки в некотором подходящем разбиении плоскости.)
5. Степень доминирования. На плоскости задано множество S из N точек. Доминирующим подмножеством множества S называется множество max(S) максимумов множества S. Степенью доминирования точки р в множестве S называется число доминирующих подмножеств, которые необходимо удалить для удаления точки р. Степень доминирования множества 5 равна максимальной степени доминирования его точек.
(a) Разработать алгоритм со сложностью O(NlogN) для вычисления степени доминирования каждой точки множества S.
(b) Оптимален ли этот алгоритм?
ГЛАВА
Близость: основные алгоритмы
В главе 4 был приведен алгоритм двух наиболее удаленных друг от друга точек множества на плоскости, имеющей сложность 0{N-\ogN). Можно было бы предположить, что алгоритм поиска двух ближайших друг к другу точек множества можно получить простым обобщением указанного алгоритма, но это не так. Две наиболее удаленные точки множества с необходимостью являются вершинами выпуклой оболочки этого множества, и для разработки быстрого алгоритма можно использовать свойство выпуклости. Две ближайшие точки совсем не обязательно имеют какое-либо отношение к выпуклой оболочке, так что для решения этой задачи должен быть разработан новый метод. Этому и будет посвящена данная глава. Мы рассмотрим большой класс задач, связанных с определением близости точек на плоскости. Наша цель будет состоять в том, чтобы решать все эти не связанные на первый взгляд между собой задачи, используя единый алгоритм, который выявляет, обрабатывает и запоминает компактным образом всю информацию относительно близости точек. Чтобы добиться этого, мы возродим классический математический объект, называемый диаграммой Вороного, представив ее в виде эффективной вычислительной структуры, позволяющей добиться огромного преимущества по сравнению с лучшими из ранее известных алгоритмов. В этой главе для штурма этого большого и трудного класса задач — задач нахождения ближайших точек или, иначе говоря, задач определения близости — будут использованы некоторые обсуждавшиеся ранее методы решения геометрических задач, такие как построение выпуклой оболочки и геометрический поиск.
Как уже говорилось выше, состояние дел в этой области вычислительной геометрии не является исключением по отношению к сложившейся в настоящее время практике: в случае плоскости имеются мощные и элегантные методы, в то время как для трех-
5.1. Набор задач
227
мерного пространства — и тем более для пространств более высокой размерности — известно очень мало и на каждом шагу исследователя подстерегают труднопреодолимые препятствия, не сулящие ничего хорошего.
Большинство задач, изученных в предыдущих главах (за исключением задачи о наиболее удаленной паре точек), основываются исключительно на свойствах инцидентности рассматриваемых геометрических объектов. Так что соответствующие результаты остаются справедливыми при применении к объектам полной группы линейных преобразований (разд. 1.3.2). Задачи, рассматриваемые в двух последующих главах, основываются на метрических свойствах, и, таким образом, справедливость результата ограничивается группой евклидовых преобразований (группой движений твердого тела).
