Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
числу задач, решение которых ищется лишь один раз и состоит в построении некоторого геометрического объекта (ближайшей пары точек, всех ближайших соседей, евклидова минимального остовного дерева и триангуляции). Далее рассматриваются две задачи поиска (см. гл. 2), которые приходится решать многократно и которые вследствие этого допускают предварительную доработку исходных данных.
Задача Б.5 (ПОИСК БЛИЖАЙШЕГО СОСЕДА). На плоскости заданы N точек. Как быстро можно найти ближайшего соседа для некоторой новой точки q, при условии что допускается предварительная обработка [Knuth (1973)]?
В пространстве размерности d эту задачу можно решить за время O(dN). Но нас интересует, как, используя предварительную обработку, сделать процедуру поиска более быстрой. Существует множество прикладных задач, в которых может быть использован такой быстрый поиск. Наиболее важной из них, по-видимому, является задача классификации. Один из методов классификации основывается на правиле ближайшего соседа [Duda, Hart (1973)]. В соответствии с этим правилом, если необходимо классифицировать объект на принадлежность к одному из заданных классов, то его следует отнести к классу, соответствующему его ближайшему соседу. Например, неизвестная
5.2. Задача о единственности элементов
233
точка U на рис. 5.5 была бы классифицирована как принадлежащая классу В.
Похожая ситуация имеет место в информационных системах при выборке информации, когда выбирается запись, наилучшим образом соответствующая записи-запросу [Burkhard, Keller (1973), Friedman, Bentley, Finkel (1977)]. В случае, когда требуется обрабатывать большое количество объектов, решая либо задачи классификации [Duda, Hart (1973)] (при распознавании речи, идентификации элементарных частиц и т. п.), либо задачи
А* В*
Л
Рис. 5.5. Правило ближайшего соседа.
выборки данных (выборка наиболее подходящего элемента), необходимо достаточно быстро выполнять поиск ближайшего соседа.
Задача Б.6 (^-БЛИЖАЙШИХ СОСЕДЕЙ). На плоскости заданы N точек. Как быстро можно найти k точек, ближайших к некоторой новой точке q, при условии что допускается предварительная обработка?
Процедура поиска k ближайших соседей использовалась при интерполяции и выделении контуров [Davis (1975)] и при классификации (правило, использующее k ближайших соседей, является более устойчивым ко всякого рода случайностям по сравнению с тем, когда решение принимается с учетом лишь единственного соседа). Хотя последняя задача представляется более сложной, чем задача Б.5, далее будет показано, что обе они могут быть решены с использованием аналогичных геометрических структур (разд. 6.3.1).
5.2. Задача о единственности элементов
Изучая вычислительную сложность некоторой задачи, т. е. получая нижние оценки для некоторых важных параметров, таких как время, необходимое для решения задачи, и используемый объем памяти, мы часто пытаемся преобразовать (или.
234
Гл. 5. Близость- основные алгоритмы
иначе говоря, свести) некоторую хорошо изученную задачу, для которой известны нетривиальные нижние оценки, к рассматриваемой (разд. 1.4).
Примеры такого подхода стали теперь классическими, и мы уже сталкивались с ними при изучении вычислительной геометрии. Напомним хотя бы о сведении задачи сортировки (в рамках модели деревьев вычислений) к задаче построения упорядоченной выпуклой оболочки множества точек. Другим известным примером является задача ВЫПОЛНИМОСТЬ, часто используемая при доказательстве ЛФ-полноты задач [Garey, Johnson (1982)]. Вполне естественно называть такие фундаментальные задачи, играющие роль базовых для классов задач, задачами-прототипами или вычислительными прототипами.
Для первых четырех задач, представленных в предыдущем разделе, довольно легко разработать прямые алгоритмы с полиномиальной оценкой для времени. И поэтому вполне естественно попробовать в качестве возможного прототипа задачу сортировки. Хотя мы не можем исключить возможность того, что сортировка может оказаться подходящим прототипом, но до сих пор для всех четырех задач Б.1—Б.4 соответствующее преобразование не найдено. Однако, к счастью, можно использовать другой прототип —ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ [Dobkin, Lipton (1979)]. Эта задача формулируется следующим образом.
Задача (ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ). Даны N действительных чисел. Определить, имеются ли среди них хотя бы два равных.
Получим для задачи ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ нижнюю оценку временной сложности в рамках модели алгебраических деревьев решений.
Множество {хи xN} из /V действительных чисел можно рассматривать как точку (х\.....xN) в Е". Используя терминологию, введенную в разд. 1.4. обозначим через W <= Еы множество истинности для задачи ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ на множестве {хи ..... xN) (т. е. W содержит все точки,
любая пара координат которых различна). Утверждается, что W имеет ЛИ компонент связности. Действительно, любой перестановке я множества {1, 2, MN) соответствует множество точек в EN
Wn = {(Xx, ... XW) г *я-(|) <ХЛ(2) < ¦ ¦ ¦ <XMN)}.
