Задача по стереометрии

pgkorotk

Есть молекула в виде набора координат атомов. Вокруг нее можно описать параллелепипед многими способами. Как найти параллелепипед самого малого объема? Спасибо :)

blackout

Параллелепипед или прямоугольный параллелепипед? Кстати, слова "молекула" и "атом" не нужны.

Katerina555

прямоугольный

iri3955

Строим выпуклую оболочку A.
Рассмотрим такой параллелепипед. И построим колонну из них параллельными переносами вдоль оного из рёбер.
Получим много копий A. Если они друг друга не касаются, то их можно ужать, провести заново плоскость, их разделяющую, таким образом
по асимптотике, объём одного параллелепипеда уменьшится. Это значит, что они касаются.
То есть для каждого ребра параллелепипеда l, есть 2 точки на поверхности A (X и Y что l = XY и существуют параллельные опорные плоскости, проходящие, через X и Y.
Каждая из точек может быть либо вершиной, либо лежать на ребре, либо на грани. Можно перебрать все варианты (безотносительно положения точки на ребре или грани, этого, кажется, достаточно для построения параллелепипеда) и найти минимальный. Правда сложность порядка N^6. Но проще сходу не придумывается.
И только малая часть пар имеют опорные плоскости.
UPD
Не, с прямоугольным не прокатит
Оставить комментарий
Имя или ник:
Комментарий: