Cтраница 1
Алгоритмы построения выпуклой оболочки, основанные на методе разделяй и властвуй, разбивающие исходное множество точек на две части, строящие выпуклую оболочку для каждой из этих частей и затем объединяющие их за линейное время, являются геометрическими аналогами алгоритма сортировки слиянием. Алгоритм, строящий выпуклую оболочку в реальном времени, является аналогом алгоритма сортировки вставками. Аналоги алгоритма быстрой сортировки обсуждались в разд. [1]
Придумайте алгоритм построения выпуклой оболочки, осно ванный на хранении неупорядоченного множества ребер, где ( с математической точки зрения) ребро - это неупорядоченная пара точек плоскости. [2]
Нет проблемы разработать открытый алгоритм построения выпуклой оболочки, если время обработки не принимается во внимание. Можно проявить большую сообразительность, вспомнив, что алгоритм Грэхема состоит из двух отдельных шагов - сортировки и обхода. [3]
Теперь мы переходим к описанию алгоритмов построения выпуклой оболочки. [4]
Целью этого раздела является разработка открытых алгоритмов построения выпуклой оболочки, в полной мере удовлетворяющих конкретным требованиям. [5]
Как уже отмечалось ранее, результатом работы алгоритмов построения выпуклой оболочки должно быть описание политопа, представляющего выпуклую оболочку. В предыдущем разделе было показано также, что оценка для метода под-над превышает эту нижнюю оценку на множитель 0 ( N), и для а 3 ( а в этом случае нечетное число) это лучшее, что можно ожидать для открытого метода. В трехмерном случае это дало бы оценку О ( N 3 / 2J log N - - О ( N log N) С другой стороны, нижняя оценка в общем случае в точности равна Q ( N log N) ( см. разд. [6]
Обозначим через Т ( т) трудоемкость алгоритма построения выпуклой оболочки для множества из т точек. [7]
Нет ничего удивительного в том, что как открытый алгоритм построения выпуклой оболочки, рассмотренной в разд. Однако в представлениях оболочки в этих двух подходах имеется существенное различие. При первом подходе каждый узел дерева представляет некоторую точку множества. При втором подходе только листья дерева используются для представления точек, а каждый внутренний узел представляет В-оболочку точек, соответствующих его листьям. [8]
После перехода к двойственной системе неравенств, нужно будет применить какой-либо из разнообразных алгоритмов построения выпуклой оболочки множества точек, и вслед за тем совершить обратное преобразование двойственности. Охарактеризовать эти преобразования нетрудно. [9]
Заметим, что модель вычислений, основанная на деревьях решений, использовавшаяся во всех рассмотренных до сих пор алгоритмах построения выпуклой оболочки, исключает использование функции взятия целой части. [10]
В работе [8] приведен алгоритм построения выпуклой оболочки в трехмерном пространстве без анализа временной сложности алгоритма. [11]
Алгоритм объединения оболочек подмножеств описан в [31], где также описаны и другие алгоритмы этого раздела. В этой же книге описаны алгоритмы построения выпуклой оболочки в пространстве произвольной размерности. [12]
Прежде чем обсуждать чрезвычайно важный результат Стили - Яо и Бен-Ора, давайте посмотрим, почему модель линейного дерева решений не подходит для нашей задачи. Коротко можно сказать, что не существует алгоритма построения выпуклой оболочки, использующего исключительно линейные проверки, поэтому модель линейного дерева решений не применима. [13]
В самом деле, в то время как в открытом алгоритме построения выпуклой оболочки из разд. Эта задача рассматривалась Овермарсом и Ван Леювеном. [14]
В этой главе преследуются две цели. Первая - обсуждение вариантов и частных случаев задачи построения выпуклой оболочки, а также анализ поведения алгоритмов построения выпуклой оболочки в среднем. Вторая цель состоит в обсуждении приложений, в которых используется выпуклая оболочка. Новые задачи будут сформулированы и обсуждены в том виде, в каком они возникают в этих приложениях. Многообразие этих задач должно убедить читателя в важности задачи построения выпуклой оболочки как для практики, так и в качестве фундаментального средства для решения задач вычислительной геометрии. [15]