Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 87

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 81 82 83 84 85 86 < 87 > 88 89 90 91 92 93 .. 180 >> Следующая


Ясно, что

W= U Wn

и при этом W-j являются компонентами связности, а #(и?) = ЛП. Отсюда как следствие теоремы 1.2 получаем

5.3. Нижние оценки

235

Следствие 5.1. В рамках модели алгебраических деревьев вычислений любой алгоритм, определяющий, являются ли элементы множества из N действительных чисел различными, требует Q (N log N) проверок.

Этот важный результат будет использован в следующем разделе.

Замечание. В вычислительной геометрии используются три важные задачи-прототипа, имеющие небольшую сложность Q,{N\ogN). Это — сортировка, определение крайних точек и проверка единственности элементов множества. Сведение этих задач друг к другу — дело, далеко не простое. Но все они обладают одной общей и важной чертой: нижняя оценка сложности этих задач получена в результате анализа мощности множества перестановок из N элементов (симметрической группы Sat). И хотя довольно соблазнительно найти общего «предка» этих задач-прототипов — нечто вроде ИДЕНТИФИКАЦИЯ ПЕРЕСТАНОВКИ, — но мы не видим пути, ведущего к естественной формулировке подобной задачи.

5.3. Нижние оценки

Как обычно, прежде чем приступить к изучению алгоритмов решения задач, перечисленных в разд. 5.1, обсудим их сложность. Начнем с задач поиска ПОИСК БЛИЖАЙШЕГО СОСЕДА и /fe-БЛИЖАИШИХ СОСЕДЕЙ.

В качестве вычислительного прототипа возьмем задачу ДВОИЧНЫЙ ПОИСК. Легко можно показать, что

ДВОИЧНЫЙ ПОИСК ос оо) БЛИЖАЙШИЙ СОСЕД.

Пусть заданы N действительных чисел х\, х2, .... Хц. В результате двоичного поиска определяется число Xi, ближайшее к числу q, задаваемому в запросе на поиск. (При этом допускается предварительная обработка!) Но эту же самую задачу можно представить и в геометрической формулировке, сопоставив каждому числу Xi точку на плоскости с координатами (xi, 0). И таким образом, поиск ближайшего соседа приведет к тому же ответу, что и двоичный поиск. Используя один из основных фактов теории информации, получаем следующую теорему:

Теорема 5.1. Для поиска ближайшего соседа точки в пространстве произвольной размерности необходимо выполнить Q(logiV) сравнений (в худшем случае).

Если, оставаясь в рамках модели деревьев решений, предположить, что число q с равной вероятностью может принадлежать любому из N + 1 интервалов, определяемых числами Xi, то

236

Гл. 5. Близость: основные алгоритмы

теорема 5.1 дает оценку поведения в среднем для любого алгоритма поиска ближайшего соседа.

Что касается задачи ^-БЛИЖАЙШИХ СОСЕДЕЙ, то, положив k=l, немедленно получаем сведение ПОИСК БЛИЖАЙШЕГО СОСЕДА ос ^-БЛИЖАЙШИХ СОСЕДЕЙ. Таким образом, теорема 5.1 применима и к задаче &-БЛИЖАЙШИХ СОСЕДЕЙ.

Разобравшись с задачами поиска, обратимся теперь к задачам Б.1—Б.4. На рис. 5.6 показана диаграмма сводимости задач (на диаграмме символ ос заменен стрелкой).

ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ-»- БЛИЖАЙШАЯ ПАРА (3.1)

Начнем с рассмотрения сводимости ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ ос„ БЛИЖАЙШАЯ ПАРА. Пусть задано множество действительных чисел {х\, х2, . . ., xN). Будем рассматривать их как точки на прямой у = 0, пытаясь найти ближайшую пару точек. Если расстояние между точками, образующими ближайшую пару, не равно нулю, то все точки множества различны. Так как множество точек, заданное в одномерном пространстве, всегда можно вложить в пространство размерности к, то естественным образом получаем обобщение этого сведения.

Сведение БЛИЖАЙШАЯ ПАРА осд, ВСЕ БЛИЖАЙШИЕ СОСЕДИ очевидно, так как одна из пар, полученных в результате решения последней задачи, будет ближайшей и она может быть определена с помощью O(N) сравнений.

Рассмотрим теперь задачу ЕМОД (Б.З). В предыдущем разделе уже говорилось о том, что ЕМОД содержит кратчайшее ребро евклидова графа на множестве из N точек, и, следовательно, задача БЛИЖАЙШАЯ ПАРА тривиальным образом сводится к ЕМОД за линейное время. Однако можно также показать, что

СОРТИРОВКА ocN ЕМОД.

5.3. Нижние оценки

237

Действительно, рассмотрим множество из N действительных чисел {xi.....xN). Рассматривая каждое число xi как точку (xit 0)

на плоскости, построим соответствующее множество ЕМОД. В получившемся ЕМОД вершины, соответствующие числам xi и Xj, соединены ребром тогда и только тогда, когда и Xj образуют пару последовательных чисел в упорядоченном множестве. Решением задачи ЕМОД является список, содержащий N—1 пар (i, /), каждая из которых определяет ребро дерева. Не составляет труда преобразовать этот список в упорядоченный список чисел Xi, затратив на это время 0(N). (Читателю предоставляется сделать это в качестве простого упражнения.)

Рис. 5.7. Иллюстрация к получению нижней оценки сложности решения задачи ТРИАНГУЛЯЦИЯ.

И наконец, рассмотрим задачу ТРИАНГУЛЯЦИЯ (Б.4) и покажем, что

СОРТИРОВКА ccN ТРИАНГУЛЯЦИЯ.

Рассмотрим множество из N точек {хи х2.....xN}, показанное на рис. 5.7. iV — 1 точек множества лежат на одной прямой, а одна точка находится вне этой прямой. Триангуляция этого множества может быть выполнена единственным способом, как это показано на рисунке. Список ребер, порождаемый алгоритмом триангуляции, можно использовать для получения упорядоченного списка чисел xi, затратив на это дополнительно O(N) операций. Таким образом, необходимо сделать Q(NlogN) сравнений ').
Предыдущая << 1 .. 81 82 83 84 85 86 < 87 > 88 89 90 91 92 93 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed