2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 09:56 
При изменении $H$ кривая просто перемещается вверх-вниз? Или как-то сложнее меняется?

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:03 
slavav в сообщении #1201101 писал(а):
При изменении $H$ кривая просто перемещается вверх-вниз? Или как-то сложнее меняется?

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:13 
Ищите двоичным поиском по $H$.

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:26 
slavav в сообщении #1201108 писал(а):
Ищите двоичным поиском по $H$.

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

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 06:18 
Аватара пользователя
Adventor в сообщении #1201084 писал(а):
Однако, всё упирается в п.2. Как искать точку касания двух кривых?

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 20:20 
Pavia в сообщении #1201406 писал(а):
Adventor в сообщении #1201084 писал(а):
Однако, всё упирается в п.2. Как искать точку касания двух кривых?

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

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

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

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 21:24 
Опишите хитрый способ.
Есть ли какая-нибудь связь между функциями $B(H_1)$ и $B(H_2)$?

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 22:36 
slavav в сообщении #1201620 писал(а):
Опишите хитрый способ.
Есть ли какая-нибудь связь между функциями $B(H_1)$ и $B(H_2)$?

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

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 22:50 
Тогда глядя на разницу $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}$?

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 23:22 
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 --

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

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение19.03.2017, 02:30 
Выберете любой $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}}$ - искомая функция.

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение20.03.2017, 13:22 
slavav, благодарю. Выглядит разумно.

 
 
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение20.03.2017, 16:24 
Adventor в сообщении #1201084 писал(а):
4. Повторяем п.2-3 пока площадь не станет убывать.

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

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

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group