Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Q(f{N)) служит для обозначения множества всех функций g(N) таких, что существуют положительные константы Ci, С2 и No, для которых Cif(N)^ g(N)sz: C2f(N) при всех N ^ N0.
o(f(N)) служит для обозначения множества всех функций g(N) таких, что для всех положительных констант С существует некое N0, при котором g(N)^ Cf(N) для всех N ^ N0 (или, что то же самое, lim g(N)/f(N) = 0).
Итак, 0(f(N)) используется для указания функций, которые не более чем в постоянное число раз превосходят f(N), этот способ нужен для описания верхних оценок; напротив, Q(f(N)) используется для указания функций, которые не менее чем в постоянное число раз превосходят f(N) —аналогичный способ, но для нижних оценок. Наконец, Q(f(N)) используется для указания функций того же порядка, что и f(N); этот способ нужен для «оптимальных» алгоритмов.
Предыдущее обсуждение было сосредоточено на времени счета алгоритма. Другая важная мера его эффективности — это
20 Гл. 1. Введение
пространство, обычно совпадающее с объемом памяти, использованной алгоритмом. Несомненно, пространственная и временная сложности как функции от размеров задачи являются двумя фундаментальными оценками эффективности при анализе алгоритмов.
Главная цель данной книги, по сути, заключается в представлении алгоритмов для геометрических задач и оценке их сложности для худшего случая. Сложность для худшего случая — это максимальная мера эффективности данного алгоритма для всех задач данного размера, и ее нельзя путать со сложностью в среднем (или ожидаемой), которая отличается тем, что дает оценку наблюдаемого поведения этого алгоритма. К сожалению, анализ поведения в среднем значительно более сложная вещь, чем анализ худшего случая, по двум причинам: во-первых, существенные математические трудности возникают, даже если удачно выбрано исходное распределение; во-вторых, часто с трудом достигается согласие в том, что именно выбранное распределение является реальной моделью изучаемой ситуации. Вот почему преобладающее большинство результатов связано с анализом худших случаев; соответственно и в данной книге будут лишь изредка обсуждаться результаты поведения в среднем.
Еще один важный момент, который следует отметить, связан с тем, что обозначения «порядка» скрывают мультипликативные константы. Следовательно, оценка сложности достигает своей законной силы только при весьма больших размерах задачи; именно поэтому такой подход называется асимптотическим анализом. Следовательно, вполне вероятно,— и действительно часто бывает так, — что при малых размерах задачи наиболее пригоден алгоритм, который асимптотически не оптимален. Это предостережение никак нельзя игнорировать при выборе алгоритма для конкретного приложения.
1.2.2. Несколько замечаний об общих алгоритмических методах
Эффективные алгоритмы для геометрических задач часто конструируются при помощи общих методов теории алгоритмов, таких как «разделяй и властвуй», балансировка, рекурсия и динамическое программирование. Превосходное обсуждение этих методов содержится в ставших теперь классическими книгах по анализу и проектированию алгоритмов (см., например, [Aho, Hopcroft, Ullman (1974)]), и было бы излишеством повторять его здесь.
Однако существует метод, который подсказан — исключительно и естественно — природой некоторых геометрических задач. Этот метод называется заметанием, и наиболее часто ветре-
1.2. Алгоритмические основы 21
чаются примеры плоского заметания (в двух измерениях) и пространственного заметания (в трех измерениях). Сейчас опишем главные черты плоского заметания; его можно весьма просто обобщить на случай трех измерений.
Для определенности иллюстрируем этот метод на примере конкретной задачи (обсуждаемой во всех подробностях в разд. 7.2.3): дано множество отрезков на плоскости, надо найти все их пересечения. Возьмем прямую / (предположим без ограничения общности, что она вертикальная), которая разбивает данную плоскость на левую и правую полуплоскости. Допустим, что каждая из этих полуплоскостей содержит концы заданных отрезков. Очевидно, что решение нашей задачи есть объединение решений для каждой из двух полуплоскостей; поэтому, если предположить, что у нас уже есть множество точек пересечения слева от /, то на это множество не будут влиять отрезки, расположенные справа от /. Теперь заметим, что пересечение (искомое) может произойти только между такими двумя отрезками, чьи пересечения с некоторой вертикалью смежны; итак, если построить все вертикальные сечения отрезков заданного множества, то наверняка будут обнаружены и все искомые пересечения. Однако этой (неразрешимой) задачи построения (континуально) бесконечного множества всех секущих вертикалей можно избежать, если заметить, что плоскость разбивается на вертикальные полосы, ограниченные или концами отрезков, или точками их пересечения, и такие, что вертикальный порядок точек пересечения вдоль любой вертикальной секущей в такой полосе постоянен. Таким образом, все, что надо сделать, состоит в скачке с левого края такой полосы на ее правый край с обновлением порядка точек пересечения вертикали и поиском новых пересечений среди «соседних» в этом порядке отрезков.
