Наименьший периметр квадрата, Включающий в себя все точки

Здравствуйте. Есть задачка, которую я не могу решить.
Есть N точек. Нужно построить квадрат минимальной площади, содержащий внутри и на границе все точки. Стороны квадрата могут не быть параллельны осям.
Надеюсь на вашу помощь. Спасибо

0

При чём тут ориентация? Если окружность полностью "окружает" точки, то квадрат снаружи окружности в любом положении поглотит эти же точки - но он скорее всего не будет минимальным. Может попробовать вращать квадрат на 90° (допустим по 1° - всего 90 шагов) и пытаться его уменьшить в разных положениях до соприкосновения с точками? В каком-то положении он достигнет минимума.

Добавлено через 5 минут
На 180 градусов?

0

Сообщение от alexu_007 При чём тут ориентация?

Чего? Вся суть данной задачи, с самого начала - найти ту ориентацию охватывающего квадрата, при котором он будет минимальным. В этом заключается все 100% данной задачи. Все остальное - побочные тривиальные мелочи.

А вы спрашиваете "при чём тут ориентация"??? Остается только удивленно развести руками...

Сообщение от alexu_007 Если окружность полностью "окружает" точки, то квадрат снаружи окружности в любом положении поглотит эти же точки - но он скорее всего не будет минимальным.

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

Сообщение от alexu_007 В каком-то положении он достигнет минимума.

Спасибо, кэп. Разумеется, в каком-то положении он достигнет минимума. В нахождении этого положения, еще раз, вся суть задачи и заключается.

Вся ценность упоминавшейся здесь стратегии Rotating Calipers сводится к тому, что она дискретизирует множество положений, то есть дает нам конечное множество ориентаций, которые достаточно рассмотреть, для того, чтобы гарантированно найти оптимальное решение. Однако приведенные выше контрпримеры показывают, что для задачи с квадратом тривиального применения Rotating Calipers недостаточно: оптимальная ориентация квадрата запросто может НЕ входить в тот набор ориентаций, которые генерирует Rotating Calipers.

В этом вся загвоздка и заключается.

Сообщение от alexu_007 Может попробовать вращать квадрат на 90° (допустим по 1° - всего 90 шагов) и пытаться его уменьшить в разных положениях до соприкосновения с точками?

Вы предлагаете банальности уровня "детский сад". Если вы можете предложить эффективный итеративный метод, который сходится к точному решению - предлагайте. В противном случае наивные идеи вида "вращать квадрат на 90° по 1°" - бесперспективны.

0