Дано: набор непрерывных кусочно-линейных функций, каждая со своим отдельным множеством точек излома, например (пунктирные линии относятся к специальному случаю, на них не следует обращать внимание):
Требуется: рассчитать верхнюю огибающую семейства, то есть такую кусочно-линейную функцию, значение которой в каждой точке равно максимуму из значений функций семейства в этой точке. На картинке требуется найти красную линию:
Для решения, конечно, достаточно построить множество точек излома искомой функции. Собственный алгоритм придуман и даже написан, но не хотелось бы переизобретать велосипеды. Поэтому вопрос: существует ли задача, решаемая стандартными алгоритмами, к которой сводилась бы данная задача?
Простой