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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

📎📎📎📎📎📎📎📎📎📎