Задача - построение - выпуклая оболочка
Cтраница 1
Задача построения выпуклой оболочки не только оказывается центральной для практических приложений, но является также основой для решения ряда других важных вопросов вычислительной геометрии. [1]
Для задачи построения выпуклой оболочки в многомерных пространствах случай трехмерного пространства имеет огромную важность, так как он естественным образом возникает во множестве прикладных областей, включающих машинную графику, автоматизацию проектирования, распознавание образов, исследование операций. К счастью, этот важный для приложений случай одновременно является изюминкой с точки зрения сложности вычислений. [2]
Для решения задачи построения выпуклой оболочки может быть использован и алгоритм динамического программирования 5 ], так как ее нетрудно преобразовать к форме задачи оптимизации многостадийного процесса. [3]
 |
Построение опорных прямых эквивалентно поиску пересечения в двойственном пространстве. [4] |
Лишь совсем недавно задаче построения выпуклой оболочки в Ed было уделено значительное внимание. [5]
Предположим, при решении задачи построения выпуклой оболочки, исходное множество точек было разбито на две части Si и S2, каждая из которых содержит половину точек исходного множества. Если теперь рекурсивным образом найдены отдельно CH ( Si) и CH ( S2), то каковы дополнительные затраты, необходимые для построения CH ( Si U S2), т.е. выпуклой оболочки исходного множества. [7]
Отметим здесь, что результатом решения задачи построения выпуклой оболочки на плоскости является упорядоченный список вершин, лежащих на границе выпуклой оболочки. [8]
Теперь мы готовы к тому, чтобы рассмотреть задачу построения выпуклой оболочки конечного множества точек в пространствах размерности большей двух. [9]
Задача сортировки является источником вдохновения при выработке идей решения задачи построения выпуклой оболочки. [10]
В работе [42] дан алгоритм с линейной сложностью в среднем для задачи построения выпуклой оболочки на плоскости. [11]
В этом разделе обсуждается задача, на первый взгляд имеющая интригующее сходство с задачей построения выпуклой оболочки, однако при более глубоком рассмотрении, что будет сделано несколько позже, обнаруживается ее принципиальное отличие от последней. В действительности первоначально эта задача была описана как задача о плавающих курсах валют 1): каждый гражданин Эревона имеет некоторое количество ( пакет) денег в иностранной валюте; курсы иностранных валют плавают в довольно широком диапазоне, поэтому каждый вечер человек, пакет валюты которого имеет наибольшую общую стоимость, провозглашается Королем Эревона. Каково наименьшее подмножество населения Эревона, с определенностью содержащее всех потенциальных королей. [12]
В качестве другого примера задачи, для которой с успехом может быть применен метод последовательного конструирования, который, как может быть показано, является оптимальным, рассмотрим задачу построения выпуклой оболочки множества точек на плоскости ( см. разд. Мы просто последовательно просматриваем точки и сразу же строим выпуклую оболочку для просмотренных точек. Если очередная точка лежит внутри уже построенной выпуклой оболочки, то ничего делать не надо, и эта точка просто игнорируется. В противном случае она является граничной точкой выпуклой оболочки и текущая выпуклая оболочка должна быть изменена, для чего необходимо определить две опорные прямые, проходящие через эту новую точку. Хотя два приведенных примера показывают, что метод построения решения последовательным добавлением элементов позволяет получать оптимальные решения, как правило, это не имеет места для большинства задач, рассмотренных в литературе. [13]
В качестве другого примера задачи, для которой с успехом может быть применен метод последовательного конструирования, который, как может быть показано, является оптимальным, рассмотрим задачу построения выпуклой оболочки множества точек на плоскости ( см. разд. Мы просто последовательно просматриваем точки и сразу же строим выпуклую оболочку для просмотренных точек. Если очередная точка лежит внутри уже построенной выпуклой оболочки, то ничего делать не надо, н эта точка просто игнорируется. В противном случае она является граничной точкой выпуклой оболочки и текущая выпуклая оболочка должна быть изменена, для чего необходимо определить две опорные прямые, проходящие через эту новую точку. Хотя два приведенных примера показывают, что метод построения решения последовательным добавлением элементов позволяет получать оптимальные решения, как правило, это не имеет места для большинства задач, рассмотренных в литературе. [14]
Хорошо известным примером применения этого метода является задача построения выпуклой оболочки. А именно, пусть задано множество 5 из п точек на плоскости. Ниже приведен алгоритм вычисления выпуклой оболочки множества S методом разделяй и властвуй. Здесь предполагается, что исходные данные представлены совокупностью точек, заданных своими координатами, а результатом работы алгоритма является последовательность точек, принадлежащих выпуклой озолочке. Заметим, что выпуклая оболочка множества точек на плоскости является выпуклым многоугольником. Поэтому результатом работы алгоритма является последовательность вер-шии этого выпуклого многоугольника, перечисляемых, например, в порядке обхода по часовой стрелке. [15]
Страницы: 1 2