Ответ 1
Я не знаю, что вы подразумеваете под "попробовать все возможные вращения", так как их бесконечно много, но эта основная идея действительно дает очень эффективное решение:
Первый шаг - вычислить выпуклую оболочку. Насколько это реально экономит, зависит от распределения ваших данных, но для точек, выбранных равномерно с единичного диска, ожидается, что количество точек на корпусе будет O (n ^ 1/3). Есть количество способов сделать это:
- Если точки уже отсортированы по одной из их координат, алгоритм сканирования Грэма делает это в O (n). Для каждой точки в данном порядке подключите ее к предыдущим двум в корпусе, а затем удалите каждую новую точку (единственный кандидат - соседние с новой точкой) на новом корпусе.
- Если точки не отсортированы, алгоритм подарочной упаковки - это простой алгоритм, который выполняется в O (n * h). Для каждой точки на корпусе, начиная с самой левой точки входа, проверьте каждую точку, чтобы увидеть, является ли она следующей точкой на корпусе.
h- количество точек на корпусе. - алгоритм Чена promises O (n log h), но я не совсем изучил, как это работает.
- другая идея simle заключалась бы в сортировке точек по их азимуту, а затем удалении вогнутых. Однако сначала это похоже только на O (n + sort), но я боюсь, что на самом деле это не так.
В этот момент проверка каждого угла, собранного до сих пор, должна быть достаточной (как было созвано мной и Оливером Чарльвертом, и для которых Евгений Клев [ предложил суть доказательства)). Наконец, позвольте мне обратиться к соответствующей ссылке в Lior Kogan answer.
Для каждого направления ограничивающая рамка определяется теми же четырьмя (не обязательно разными) точками для каждого угла в этом интервале. Для направлений кандидата вы получите хотя бы один произвольный выбор. Поиск этих точек может показаться задачей O (h ^ 2) до тех пор, пока вы не поймете, что крайности для рамки с выравниванием по оси - это те же крайности, с которых вы начинаете слияние, и что последовательные интервалы имеют свои экстремальные точки, одинаковые или последовательные, Назовем крайние точки A,B,C,D по часовой стрелке, а соответствующие линии, ограничивающие ограничивающий прямоугольник, A,B,C,D. 
Итак, сделайте математику. Область ограничивающего прямоугольника задается символом |a,c| * |b,d|. Но |a,c| - это только вектор (AC), проецируемый в направление прямоугольника. Пусть u - вектор, параллельный a и c, а v - перпендикулярный вектор. Пусть они плавно меняются по всему диапазону. В векторном выражении площадь становится равной ((AC).v) / |v| * ((BD).u) / |u|= {((AC).v) ((BD).u)} / {|u| |v|}. Выберем также, что u = (1,y). Тогда v = (y, -1). Если u является вертикальным, это создает небольшую проблему с ограничениями и бесконечностями, поэтому просто выберите u в этом случае горизонтально. Для численной устойчивости просто поверните на 90 ° каждый u, который находится вне (1,-1)..(1,1). Перевод области в декартовую форму, при желании, оставлен в качестве упражнения для читателя.