Вписание многогранника в многогранник , Поиск максимального объёма

[prografix]

Имеются два выпуклых многогранника. Нужно найти такое аффинное преобразование, применяя которое к первому многограннику, он будет вписан во второй и иметь максимальный объём.

[scrambrella]

Разобьём многогранник на пирамидки. Объём каждой пирамидки поменяется в одно и то же число раз при линейном преобразовании, которое легко найти.
Вписанность как система линейных неравенств - сравнением точек нашего многогранника с плоскостями граней другого многогранника.
Линейное программирование?

[prografix]

Цитата scrambrella @ 28.04.21, 20:49

Линейное программирование?

Нелинейное. Объём - это функция третьего порядка. Можно рассмотреть задачу немного проще.
Передвинем многогранники так, чтобы их центры масс находились в начале координат, и теперь будем искать линейное преобразование, применяя которое к первому многограннику, он будет вписан во второй и иметь максимальный объём. Здесь мы, убирая смещение, снижаем размерность задачи с 12 ( аффинное преобразование ) до 9 ( линейное преобразование ).

[Qraizer]

А если привлечь физику? Задать внутреннему многограннику характеристику давления и в точках соприкосновения вершин считать вектора сил, считая скелет многогранника абсолютно упругим. Есть нюанс: метод считает преобразование непрерывным, тогда как задача этого не требует, главное, чтоб результат показал пересечение тел, совпадающее с внутренним телом. Т.е. этот метод не даст вершинам внутреннего многогранника пересечь грани внешнего в процессе расчёта действия сил, поэтому если существует лучшее решение, проходящее через промежуточное худшее, оно не будет найдено.

[scrambrella]

Цитата Qraizer @ 29.04.21, 13:09

А если привлечь физику? Задать внутреннему многограннику характеристику давления и в точках соприкосновения вершин считать вектора сил, считая скелет многогранника абсолютно упругим.

Уткнётся в стенку в плохой позиции и дальше расширяться не будет.

[prografix]

Можно, конечно, решать градиентными методами, но это долго и будут локальные максимумы.

[Qraizer]

scrambrella, именно это я и написал. Если хочется что-то сказать, давай по существу.
prografix, никто не запрещает поставить множество экспериментов.
Вообще, в общем случае тут нет решения. Иначе давно б не существовало бы нерешённых задач типа этой Т.е. лучшее, что можно, пробовать по-разному и оценивать результат. ИМХО физический движок наиболее просто это реализует.

Добавлено 30.04.21, 11:59
P.S. Самому страшно: требуется максимизировать тройной интеграл в поле кватернионов на компактном многообразии, заданном ещё одним тройным интегралом. Буду признателен, если кто предложит формулировку задачи попроще.

Сообщение отредактировано: Qraizer - 30.04.21, 12:00

[prografix]

Qraizer
Формулировка такая: множество допустимых значений образует выпуклый многогранник в 9-мерном пространстве ( для второй задачи ). Нужно найти оптимальную точку. Беда в том, что она может лежать не на вершине и не на ребре многогранника, а где-то на поверхности.