Вписать кривую наибольшей площади в другую кривую

[Adventor]

Есть дискретный набор точек $A(x)$ (красная кривая), в который внутрь требуется вписать кривую $B(x)$ (зеленая) максимальной площади
(так чтобы $B(x)$ не превышало $A(x)$ для любого $x$)
Горизонтальный размер $D$ фиксирован, высота $H$ может быть любой.


Общий алгоритм я вижу такой:
1. Начинаем с левого края. Т.е. ставим кривую $B$ в крайнее левой положение.
2. Находим точку касания кривых, чтобы определить $H$. Считаем площадь.
3. Смещаем $B$ вправо на одну точку.
4. Повторяем п.2-3 пока площадь не станет убывать.
5. Смотрим при каком смещении максимальная площадь.

Однако, всё упирается в п.2. Как искать точку касания двух кривых?

[slavav]

При изменении $H$ кривая просто перемещается вверх-вниз? Или как-то сложнее меняется?

[Adventor]

slavav в сообщении #1201101 писал(а):

При изменении $H$ кривая просто перемещается вверх-вниз? Или как-то сложнее меняется?

Она не то что перемещается вверх вниз, просто масштабируется. Упрощенно нижняя граница равна нулю, верхняя произвольная положительная.

[slavav]

Ищите двоичным поиском по $H$.

[Adventor]

slavav в сообщении #1201108 писал(а):

Ищите двоичным поиском по $H$.

Мысль неясна. Что искать?

[slavav]

Для любого $H$ можно установить лежит ли шапочка под графиком функции. Существует граница $H_0$: $H > H_0$ приводит к пересечению. Эту границу можно найти двоичным поиском.

[Pavia]

Adventor в сообщении #1201084 писал(а):

Однако, всё упирается в п.2. Как искать точку касания двух кривых?

Выписываем уравнения и решаем систему уравнений. Можно численно, можно аналитически.
Но пока нет уравнений ничего вам посоветовать нельзя.

[Adventor]

Pavia в сообщении #1201406 писал(а):

Adventor в сообщении #1201084 писал(а):

Однако, всё упирается в п.2. Как искать точку касания двух кривых?

Выписываем уравнения и решаем систему уравнений. Можно численно, можно аналитически.
Но пока нет уравнений ничего вам посоветовать нельзя.

Да уравнений здесь собственно нет. Один набор точек экспериментальный, другой получается хитрым способом.

Я полагаю так что составляется массив $B$ для определенного $H$, проверяется условие что все элементы массива $B$ меньше чем элементы массива $A$. Потом увеличивается $H$, опять проверяется условие. Если условие не выполнено, значит на следующей итерации $H$ уменьшается.

Как применить двоичный поиск для этой задачи нужно подумать.

[slavav]

Опишите хитрый способ.
Есть ли какая-нибудь связь между функциями $B(H_1)$ и $B(H_2)$?

[Adventor]

slavav в сообщении #1201620 писал(а):

Опишите хитрый способ.
Есть ли какая-нибудь связь между функциями $B(H_1)$ и $B(H_2)$?

Я описывал способ вот здесь: http://dxdy.ru/topic112007.html
Вкратце это свертка.

Связь просто коэффициент. $B(H_1)$ = $B(H_2)C$

[slavav]

Тогда глядя на разницу $A - B(H_0)$ можно сразу вычислить $ H_{\max}: A - B(H_{\max}) \geqslant 0$

-- 18.03.2017, 22:52 --

Правда ли что $B(H_1) = B(H_2)\frac{H_1}{H_2}$?

[Adventor]

slavav в сообщении #1201642 писал(а):

Правда ли что $B(H_1) = B(H_2)\frac{H_1}{H_2}$?

Да, это правда.

-- Сб мар 18, 2017 23:24:19 --

slavav в сообщении #1201642 писал(а):

Тогда глядя на разницу $A - B(H_0)$ можно сразу вычислить $ H_{\max}: A - B(H_{\max}) \geqslant 0$

Про разницу не понял.

-- Сб мар 18, 2017 23:27:07 --

Вернее, если я правильно понял, это будет тоже самое о чем я написал ранее. Разница это такой же массив что и изначальные "кривые", и все его элементы д.б. не отрицательны, и эта разность д.б. минимальна.

[slavav]

Выберете любой $H_0$. Вычислите $C$:
$C = \min\limits_{x: B_{H_0}(x) > 0} \frac{A(x)}{B_{H_0}(x)}$

$H_{\max} = H_{0}C$
$B_{H_{\max}}$ - искомая функция.

[Adventor]

slavav, благодарю. Выглядит разумно.

[realeugene]

Adventor в сообщении #1201084 писал(а):

4. Повторяем п.2-3 пока площадь не станет убывать.

Это неверно. Кривая у вас двупараметрическая: параметрами являются положение левого края и высота. Для данного положения левого края можно найти максимальную высоту, как описано выше. Но вот этот максимум высоты (и соответственно, максимум площади вписанной кривой) в зависимости от положения левого края не обязан быть единственным. Вы ищете глобальный максимум, но рискуете поймать локальный.

Не знаю, зачем вам это нужно, но, вообще говоря, обсуждаемый метод чувствителен к шумам.