Cтраница 2
Хорошо известным примером применения этого метода является задача построения выпуклой оболочки. А именно, пусть задано множество S из п точек на плоскости. Ниже приведен алгоритм вычисления выпуклой оболочки множества S методом разделяй и властвуй. Здесь предполагается, что исходные данные представлены совокупностью точек, заданных своими координатами, а результатом работы алгоритма язляется последовательность точек, принадлежащих выпуклой озолочке. Заметим, что выпуклая оболочка множества точек на плоскости является выпуклым многоугольником. Поэтому результатом работы алгоритма является последовательность вершин этого выпуклого многоугольника, перечисляемых, например, в порядке обхода по часовой стрелке. [16]
В этой главе преследуются две цели. Первая - обсуждение вариантов и частных случаев задачи построения выпуклой оболочки, а также анализ поведения алгоритмов построения выпуклой оболочки в среднем. Вторая цель состоит в обсуждении приложений, в которых используется выпуклая оболочка. Новые задачи будут сформулированы и обсуждены в том виде, в каком они возникают в этих приложениях. Многообразие этих задач должно убедить читателя в важности задачи построения выпуклой оболочки как для практики, так и в качестве фундаментального средства для решения задач вычислительной геометрии. [17]
Прежде чем закончить этот раздел, отметим, что метод Грэхема явным образом использует сортировку. Аналогично тому, как исследование сортировки показало, что не существует одного алгоритма, лучшего во всех случаях, мы увидим, что то же самое справедливо и для задачи построения выпуклой оболочки. Давайте продолжим исследование комбинаторной геометрии в поисках идей, способных привести к иным алгоритмам построения выпуклой оболочки. [18]
Прежде чем переходить к описанию алгоритма решения задачи о максимумах, уместно оценить ее сложность, получив нижнюю оценку для времени работы любого алгоритма отыскания максимумов в рамках модели деревьев вычислений. В частности, приводимое ниже рассуждение относится к несколько более слабому случаю модели линейных деревьев решений, известному как модель деревьев сравнений, хотя область применения полученных результатов можно расширить и на более сильный случай. В модели деревьев сравнений число аргументов линейной функции ограничено двумя переменными. Как это уже было в случае задачи построения выпуклой оболочки ( разд. [19]
В этой главе преследуются две цели. Первая - обсуждение вариантов и частных случаев задачи построения выпуклой оболочки, а также анализ поведения алгоритмов построения выпуклой оболочки в среднем. Вторая цель состоит в обсуждении приложений, в которых используется выпуклая оболочка. Новые задачи будут сформулированы и обсуждены в том виде, в каком они возникают в этих приложениях. Многообразие этих задач должно убедить читателя в важности задачи построения выпуклой оболочки как для практики, так и в качестве фундаментального средства для решения задач вычислительной геометрии. [20]