Вам же минимальный по объему паралеллипипед нужен? Это довольно сложная задача. Даже на плоскости искать прямоугольник не очень приятно.
Кажется, есть эффективное решение через численную оптимизацию и троичный поиск.
Введем функцию f(a,b) - минимальный объем параллелипипеда, повернутого на угол a вдоль оси oz и потом угол b вдоль ox. Ну или это эйлеровы углы, если хотите.
Вам надо найти минимум этой функции. Утверждение: если зафиксировать a, то двигая b функция будет переодическая с двумя экстремумами. Ну, потому что поворот на 90 градусов взвращает все как было, только оси местами меняются. Значит, на ней можно что-то вроде тернарного поиска запускать (об этом дальше).
Если же ввести функцию g(a) =Min_b(f(a,b)), то она, похоже будет такая же. По ней тоже можно такой же поиск запустить.
Итого, 2 вложенных тернарных поиска, в внутри легче все точки повернуть на -b и -a градусов и потом взять обрамляющий параллелипипед, параллельный осям координат (min/max по трем координатам за 1 проход).
В тернарном поиске делим отрезок всех углов на 3 части, считаем значение функции в двух промежуточных и крайних точках. Дальше придется повозиться со случаями, их много (12), Функция может сначала иметь максимум, потом минимум, или наоборот. И 6 вариантов, как 2 промежуточные точки лягут на 3 отрезка (возрастание,убываниние, возрастание или убывание, возрастание, убывание). Тут надо их все аккуратно нарисовать, подумать, какие соотношения четырех точек позволяют выкинуть один из трех отрезков между точками.
Возможно, придется вообще считать производные (изменять чуть-чуть угол, считать функцию и смотреть, как она поменялась). Тогда будет сильно проще решить, какой из отрезков выкинуть. Ну или тогда можно метод Ньютона применять (считая вторую производную функции численно).
Это будет что-то вроде O(n log^2 n).
Или можно просто случайным образом или с малым шагом перебирать разные углы поворота. Поворачивать все точки и искать параллельный осям координат параллелипипед (просто беря min/max по трем координатам). Для 800 точек можно 10000 углов перебрать и это займет лишь 100мс на современном железе.
Это сильно проще в реализации и, хоть и не найдет самый оптимальный параллелипипед, на глаз будет сложно это заметить.
Edit: вообще, кажется, там 3 угла, а не 2. Ну появляется еще третья функция t(a,b,c). и лишний Log n в сложности. Перебирать углы становится еще хуже, но все еще возмоно.
