Выпуклая оболочка и max/min набора линейных функций

Задача построения выпуклой оболочки множества точек на плоскости двойственна задаче нахождения максимума и минимума набора линейных функций. Существует связь между алгоритмами построения выпуклой оболочки и алгоритмами нахождения максимума и минимума набора линейных функций.
В данной статье рассматриваются алгоритмы Джарвиса и Грэхема построения выпуклой оболочки и строятся соответствующие им алгоритмы нахождения максимума и минимума набора линейных функций.



Задача вычисления максимума и минимума набора линейных функций формулируется следующим образом. Дано линейных функций вида . (Здесь — независимая переменная, угловой коэффициент равен , начальная ордината равна .) Требуется вычислить функцию-максимум и функцию-минимум .
Графиком линейной функции является прямая. Графиком функции-максимума является ломаная. График функции-минимума — это также ломаная (см. рис. 1).


Рис. 1. Графики функции-максимума и функции-минимума .

Будем считать, что все угловые коэффициенты различны, причем линейные функции расположены в порядке возрастания угловых коэффициентов, то есть , что эквивалентно условию .

Рассмотрим два алгоритма построения ломаной — графика функции-максимума . Ломаную — график функции-минимума — можно построить аналогичным образом.

Вначале сформулируем первый алгоритм построения ломаной — графика функции — из наглядных соображений, а затем докажем правильность этого алгоритма. На рисунке 2 представлена иллюстрация к первому алгоритму.


Рис. 2. Иллюстрация к первому алгоритму построения ломаной — графика функции-максимума .

Искомую ломаную — график функции — будем строить «слева направо», то есть последовательно от меньших значений абсциссы до бóльших значений. Из рисунка 2 видно, что при достаточно маленьких значениях значение функции совпадает со значением функции . (Функции расположены в порядке возрастания угловых коэффициентов, поэтому — это функция с наименьшим угловым коэффициентом.)

Вначале прямая — график функции — это «текущий максимум». Найдем точки пересечения прямой — графика функции — со всеми остальными прямыми и выберем точку пересечения с наименьшей абсциссой. Обозначим эту наименьшую абсциссу , пусть это абсцисса точки пересечения прямой — графика функции — с прямой — графиком функции . Теперь прямая — график функции — становится «текущим максимумом».

Далее проделываем с прямой — графиком функции — те же действия, что и с прямой — графиком функции . Найдем точки пересечения прямой — графика функции — с прямыми — графиками функций — и выберем точку пересечения с наименьшей абсциссой. Обозначим эту наименьшую абсциссу , пусть это абсцисса точки пересечения прямой — графика функции — с прямой — графиком функции . Прямая — график функции — становится «текущим максимумом».

Далее те же действия проделываем с прямой — графиком функции , потом с прямой — графиком функции — и так далее, пока «текущим максимумом» не станет прямая — график функции . Когда «текущим максимумом» станет прямая — график функции , — процесс построения ломаной — графика функции — следует завершить. Из рисунка 2 видно, что при достаточно больших значениях k значение функции совпадает со значением функции .

На выходе алгоритма мы получим числовую последовательность , в которой . Зная последовательность , можно вычислить последовательность : равняется абсциссе точки пересечения прямой — графика функции — с прямой — графиком функции . Эти две числовые последовательности удовлетворяют следующим условиям:

• при
• при для
• при

Сформулируем наш алгоритм более кратко. Будем использовать следующее обозначение: через обозначим абсциссу точки пересечения прямых — графиков функций и

Вначале полагаем .

Далее для выполняем следующие действия (выполняем цикл).

Среди чисел , где , выберем наименьшее. Положим равным номеру , при котором достигается минимум, а положим равным . Таким образом, можно записать.

Если на каком-то шаге оказалось, что выполняется условие , то нужно положить и завершить выполнение цикла.

Переформулируем наш алгоритм.

Вначале полагаем .

Далее повторяем следующую последовательность шагов.

1. Если , то полагаем и завершаем выполнение данной последовательности шагов.
2. Число находим из условия , полагаем .
3. Увеличиваем на 1.

Теперь запишем алгоритм на языке псевдокода.


Как вычислить ? Число является корнем уравнения относительно неизвестного . Решим это уравнение.

Таким образом, .
Отметим, что .
Время выполнения рассмотренного алгоритма — O(ns).

Доказать правильность работы данного алгоритма можно методом математической индукции.

Задача вычисления максимума и минимума набора линейных функций тесно связана с задачей построения выпуклой оболочки множества точек на плоскости.
Рассмотрим множество точек на плоскости. Выпуклой оболочкой этого множества точек называется наименьший выпуклый многоугольник, содержащий все точки данного множества (см. рис. 3)
[статья про выпуклые оболочки на Хабре].


Рис. 3. Выпуклая оболочка.

Выпуклая оболочка состоит из двух частей: так называемой верхней оболочки и так называемой нижней оболочки (см. рис. 4). Верхняя оболочка и нижняя оболочка — это ломаные, соединяющие самую левую точку с самой правой.


Рис. 4. Верхняя и нижняя оболочки.

Давайте будем проектировать точки на ось ординат Oy во всех возможных направлениях. А именно, проведем через точку прямую с угловым коэффициентом и найдем точку пересечения этой прямой с осью Oy — эта точка пересечения и есть проекция точки на ось ординат (см. рис. 5).


Рис. 5. Проекция точки на ось ординат.

Легко доказывается, что проекция точки на ось Oy имеет ординату .
Таким образом, есть не что иное, как наибольшая ордината проекции, а — это наименьшая ордината проекции.

Оказывается, что наибольшую ординату всегда имеет проекция одной из вершин верхней оболочки, а наименьшую ординату всегда имеет проекция одной из вершин нижней оболочки. Таким образом, при построении ломаной — графика функции-максимума — мы автоматически строим верхнюю оболочку, а при построении ломаной — графика функции-минимума — мы строим нижнюю оболочку.

В этом смысле задача построения ломаной — графика функции-максимума — эквивалентна задаче построения верхней оболочки, а задача построения ломаной — графика функции-минимума — эквивалентна задаче построения нижней оболочки. Итак, задача построения выпуклой оболочки множества точек эквивалентна задаче построения ломаной-максимума и ломаной-минимума .

Если рассмотреть описанный выше алгоритм построения ломаной-максимума с точки зрения построения верхней оболочки множества точек , то мы получим не что иное, как известный алгоритм Джарвиса построения выпуклой оболочки (см. рис. 6).


Рис. 6. Иллюстрация к алгоритму.

Из алгоритма Грэхема построения выпуклой оболочки можно получить второй алгоритм построения ломаной — графика функции-максимума (см. рис. 7).


Рис. 7. Иллюстрация ко второму алгоритму построения ломаной — графика функции-максимума .

Будем добавлять прямые по одной: сначала , затем , …, . Будем последовательно находить .
Предположим, что ломаная — график функции — уже построена. Укажем, как построить ломаную — график функции .
Можно показать, что прямая — график функции — пересекает ломаную — график функции — ровно в одной точке с абсциссой .
Ломаную — график функции — можно получить так: на промежутке эта ломаная совпадает с ломаной — графиком функции , — а на промежутке — с прямой — графиком функции .
Время выполнения данного алгоритма — O(n).
Строгое доказательство правильности второго алгоритма несколько сложнее, чем доказательство правильности первого алгоритма, поэтому оно здесь не приводится.
Таким образом, в данной статье описано два алгоритма построения ломаной-максимума — графика максимума набора линейных функций. Алгоритмы построения ломаной-минимума можно получить по аналогии.

Описанные алгоритмы приводятся в моей статье: Методы вычислительной реализации рангового метода кластеризации // Информатика и системы управления. 2012. № 1(31). С. 71–79. Там же приводится обобщение алгоритма Грэхема для решения задачи нахождения функций , , где обозначает максимальное из чисел , если выбросить наибольших из них, и указывается применение изложенного подхода для автоматизации процесса кластеризации эмпирических данных ранговым методом.