Cтраница 2
Такие вершины q будем называть критическими вершинами. Заметим, однако, что не каждая критическая вершина является вершиной окончательной выпуклой оболочки. Они являются лишь кандидатами в число таковых. По сути дела, единственное, что утверждается перед завегш. [16]
Уместно сделать следующее замечание. Если смотреть более строго, то аналогия будет довольно полной, когда все заданные точки являются вершинами выпуклой оболочки. Это вполне понятно, так как в задаче сортировки нет аналога для внутренних точек выпуклой оболочки. [17]
Естественный вопрос, который может быть задан в этом месте, состоит в том, а что же произойдет, если разрешить удалять точки. В этом случае мы больше не можем уничтожать те точки, о которых стало известно, что они не находятся на выпуклой оболочке, так как они могут вновь стать вершинами выпуклой оболочки после удаления некоторой точки выпуклой оболочки. [18]
Обратите внимание: если точка не является вершиной выпуклой оболочки, то она является внутренней точкой для некоторого треугольника ( Opq), где р и q - последовательные вершины выпуклой оболочки. Суть алгоритма Грэхема состоит в однократном просмотре упорядоченной последовательности точек, в процессе которого удаляются внутренние точки. Оставшиеся точки являются вершинами выпуклой оболочки, представленными в требуемом порядке. [19]
Значение SM определяет число строк в матрице А. Порядок следования строк - произвольный. На выходе А переформируется так, что первые N строк описывают вершины выпуклой оболочки по или однозначно против часовой стрелки; N - integer. На входе это число первых строк - точек матрицы А, над которыми строится оболочка, NSM. [20]
Для этой задачи были изобретены специальные методы. Мы не будем сейчас вникать в них, однако главнейшее можно увидеть из рассмотрения рис. 11.2, а. Отыскание этой точки сводится к сравнению ожидаемых прибылей во всех вершинах выпуклой оболочки. На рис. 11.2, а имеется только пять вершин, из них три на выпуклой оболочке, так что задача проста. Существует ряд методов расчета, но при больших матрицах они обыкновенно требуют цифровой вычислительной машины. В так называемом симплексном методе выбирают вершину на выпуклой оболочке, вычисляют минимальную прибыль и затем переходят по прямой к другой вершине, расположенной столь же высоко или еще выше, чем последняя рассмотренная. [21]