Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
5.1. Набор задач
Мы начнем с перечисления различных на первый взгляд задач, относящихся к определению близости, но которые, как мы увидим далее, близки с точки зрения процедуры их решения.
Задача Б.1 (БЛИЖАЙШАЯ ПАРА). На плоскости заданы N точек. Найти две из них, расстояние между которыми наименьшее1).
Эта задача настолько просто формулируется и настолько важна, что ее можно рассматривать как один из основных вопросов вычислительной геометрии как с точки зрения ее приложений, так и с чисто теоретической точки зрения. Например, одно из приложений этой задачи относится к системе реального времени, управляющей движением самолетов: с некоторыми упрощениями можно считать, что наибольшей опасности столкнуться подвергаются два самолета, находящиеся на наименьшем расстоянии друг от друга.
Центральный вопрос разработки алгоритма решения этой задачи состоит в том, нужно ли перебирать каждую пару точек, чтобы найти определенное таким образом минимальное расстояние. Это может быть сделано за время 0(dN2) в случае rf-мер-ного пространства (d — произвольное целое число). В одномерном случае существует более быстрый алгоритм, использующий тот факт, что каждая пара ближайших точек должна состоять из последовательных точек множества при упорядочении его по значению координаты. Таким образом, можно упорядочить Л' заданных действительных чисел за 0(N\ogN) шагов, а затем
') Может оказаться, что таких пар несколько. Будем считать, что для решения задачи достаточно найти одну такую пару точек.
8*
Гл. 5. Близость: основные алгоритмы
осуществить линейный просмотр упорядоченной последовательности (хи х2, *n) за время O(N), вычисляя при этом Xi+i — xi, i = I, ..., N — 1. Как будет показано далее, этот очевидный алгоритм является оптимальным.
Задача Б.2 (ВСЕ БЛИЖАЙШИЕ СОСЕДИ). На плоскости заданы N точек. Найти ближайшего соседа для каждой точки множества.
«Ближайший сосед» — это отношение на множестве точек 5, определяемое следующим образом: точка b является ближайшим соседом точки а (обозначается а-»-&), если
dist (а, 6) = min dist (а, с).
с eS-o
Пример графа этого отношения изображен на рис. 5.1. Заметим, что отношение «->-» не обязательно является симметричным, т. е.
Рис. 5.1. Отношение «ближайший сосед» ПаРа точек> УДОВЛет-
(имеют место a-*-b и Ь-*-а), называется взаимной парой. Если процедура выбора точек на плоскости является пуассоновским процессом, то математическое ожидание доли взаимных пар точек, согласно Пиелоу [Pielou (1977)], равно 6я/(8л + 3(3)'/2)~ 0.6215.
В математической экологии эта величина используется для выявления тенденции особей некоторого биологического вида к
') Хотя точка может иметь в качестве ближайшего соседа каждую из других точек множества, она может быть ближайшим соседом самое большее шести точек в двумерном пространстве и не более двенадцати точек в трехмерном пространстве. Это максимальное число точек, для которых некоторая точка является ближайшим соседом в пространстве размерности d, совпадает с максимальным числом единичных сфер, которые могут быть расположены таким образом, чтобы все они касались заданной единичной сферы. (Саати [Saaty (1970)] указывает, что это число не известно для d, больших 12.)
из а->- b вовсе не обязательно следует, что Ь ->-->- а. Отметим также, что точка может быть ближайшим соседом нескольких точек') (к тому же отношение «-к» не обязательно является функцией). Решением задачи Б.2 является совокупность упорядоченных пар (а, Ь), где а-^-Ь.
(«-»>) на множестве
воряющая условию симметричности отношения
5.1. Набор задач
образованию изолированных пар. Для этого вычисляется фактическое число взаимных пар и получившееся потом отношение сравнивается с указанной величиной. Другие задачи, включающие вычисление ближайших соседей, возникают при исследовании расселения видов. В этих задачах, так же как в географии (см. [Kolars, Nystuen (1974)]) и в физике твердого тела, представляет интерес распределение величин расстояний между ближайшими соседями. Очевидно, что в одномерном случае тот же самый алгоритм, основанный на сортировке и решающий задачу БЛИЖАЙШАЯ ПАРА, позволяет найти все пары ближайших соседей. В дальнейшем мы рассмотрим трудности, присущие этим двум задачам в пространствах большей размерности.
Задача Б.З (ЕВКЛИДОВО МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО). На плоскости заданы N точек. Построить дерево, вершинами которого являются все заданные точки и суммарная длина всех ребер которого минимальна.
Решением задачи является список, содержащий N — 1 пару точек. Каждая пара представляет ребро дерева. На рис. 5.2 показан пример такого дерева.
Задача построения евклидова минимального остовного дерева (ЕМОД) возникает в приложениях, касающихся различного рода сетей. Если необходимо организовать систему связи между N пунктами, соединив их кабелем, то использование ЕМОД
даст сеть минимальной СТОИМО- рис. 5.2. Минимальное остовное сти. Любопытно, что федераль- дерево множества точек на пло-ный закон придает данной про- скости, блеме дополнительную значимость: федеральные тарифы требуют, чтобы тариф за пользование междугородной линией связи был пропорционален длине минимального остовного дерева, соединяющего конечные пункты абонентов. Это расстояние должно измеряться на стандартной плоской проекции поверхности Земли1). Это имеет место несмотря на то, что Земля не является плоской и что телефонная компания может организовать реальную сеть не обязательно в виде МОД. Тем не менее расчет за услуги основывается на решении реальной задачи построения евклидова остовного дерева, которую приходится решать сотни раз в течение дня, поскольку конфигурации телефонной сети постоянно изменяются.
