2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 07:34 


10/05/09
78
Есть дискретный набор точек $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:03 


10/05/09
78
slavav в сообщении #1201101 писал(а):
При изменении $H$ кривая просто перемещается вверх-вниз? Или как-то сложнее меняется?

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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:13 
Заслуженный участник


26/05/14
981
Ищите двоичным поиском по $H$.

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:26 


10/05/09
78
slavav в сообщении #1201108 писал(а):
Ищите двоичным поиском по $H$.

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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение17.03.2017, 10:48 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 06:18 
Аватара пользователя


31/10/08
1244
Adventor в сообщении #1201084 писал(а):
Однако, всё упирается в п.2. Как искать точку касания двух кривых?

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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 20:20 


10/05/09
78
Pavia в сообщении #1201406 писал(а):
Adventor в сообщении #1201084 писал(а):
Однако, всё упирается в п.2. Как искать точку касания двух кривых?

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

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

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

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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 21:24 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение18.03.2017, 22:36 


10/05/09
78
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 
Заслуженный участник


26/05/14
981
Тогда глядя на разницу $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 


10/05/09
78
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 
Заслуженный участник


26/05/14
981
Выберете любой $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 


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

 Профиль  
                  
 
 Re: Вписать кривую наибольшей площади в другую кривую
Сообщение20.03.2017, 16:24 


27/08/16
9426
Adventor в сообщении #1201084 писал(а):
4. Повторяем п.2-3 пока площадь не станет убывать.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group