Треугольник, описанный вокруг множества точек

[Oam]

Множество точек задано своими координатами на плоскости. Для простоты на большую размерность пространства не замахиваемся. Нужно найти вершины "минимального" треугольника, вмещающего во внутрь себя это множество, т.е. параметры описанного треугольника. "Минимального" в смысле треугольника минимальной площади, но могут быть рассмотрены иные варианты определения минимальности, если вдруг окажется, что это упростит решение задачи (например, минимум суммы сторон и др.)
Что пытался делать:
1. Находил центр тяжести (ЦТ) всех точек
2. Находил точку, расположенную на самой периферии от ЦТ и располагал в ней первую вершину
3. Проводил касательные из первой вершины к "бокам" множества = две стороны треугольника
4. Двигал нормаль к линии "1-я вершина – ЦТ" до пересечения с самой дальней точкой множества = третья сторона.
Моя ошибка очевидна – во многих случаях вершина описанного треугольника не может быть расположена на одной из точек множества. Пример тому – 6 точек, стоящих в вершинах правильного шестиугольника. Описание вокруг него треугольника имеет очевидное решение, которое этим методом не найти.
Если моя задача покажется вам непосильной, то можно обсудить вариант вписывания множества не в треугольник, а в окружность. Окружность по определению "минимальна", а такая задача может иметь множество приложений (максимальное увеличение, при котором нужные объекты не выйдут за пределы кругового поля обзора микроскопа).
Пытался и ее решать тем же методом (ЦТ –> поиск периферийной –> стягивание диаметра по линии периферийная-ЦТ –> попытки двигать центр окружности в перпендикулярном направлении). К сожалению, очень легко указать примитивные случаи уже на 4-х точках, чтобы показать, что существует окружность меньшего диаметра, чем находит такой метод.
Какие будут советы?

[незваный гость]

Вообще, такими задачами занимается вычислительная геометрия. Моя любимая книжка — Препарата Ф., Шеймос М. — Вычислительная геометрия: введение, но есть и другие.

Несколько случайных соображений (для случая окружности):

1) Мне не очень понятно использование ц.т. Он, по идее, никак не связан с искомой окружностью.

2) То, что понятно сразу: можно перейти к выпуклой оболочке исходных точек. Хотелось бы, конечно, ее проредить, но непонятно как. Например, такой критерий: если точка лежит внутри минимальной окружности, натянутой на три точки, то она лежит и внутри минимальной окружности (т.е., ее можно выкинуть из дальнейшего рассмотрения) не работает.

3) Неприятности обнаруживаются сразу, уже в случае треугольника. А именно, для тупоугольного треугольника центр искомой окружности — середина длинной стороны, а для остальных — центр описанной окружности.

[нг]

Все же эта область заметно ближе к Computer Science.

[uni]

Институт прикладной математики имени М.В.Келдыша РАН:
http://www.keldysh.ru/papers/2006/prep0 ... 06_09.html

Там есть интересная картинка. Может сначала построить суперструктуру -- квадрат вокруг точек, а потом вокруг квадрата -- треугольник. Потом треугольник в данном положении уменьшить до соприкосновения со множеством точек. Это одно значение площади. Затем исходный треугольник (построенный по квадрату) поворачиваем на небольшой градус и опять уменьшаем -- второе значение площади. Так делаем, поворачивая от 0 до $2\pi$. Вроде бы перебрали все варианты.

[незваный гость]

Имеет смысл соотнести с выпуклой оболочкой: можно подумать, не должен ли этот треугольник включать ребро/сторону выпуклой оболочки. Если должен, то мы можем поворачивать сразу на некоторый угол.

Одна из проблем подхода — треугольников много разных, не обязательно равносторонних. Поэтому после поворота надо фактически искать заново.

[uni]

Примерно вот так:

Далее как описано выше. Сдвигаем рёбра в сторону точек, причём, делая это параллельным переносом. У нас получится "оптимальный" треугольник. Поскольку он равносторонний, то вокруг него можно описать окружность очень просто и сразу найти центр. Гуляя от центра окружности, можно и её постепенно сжимать, находя самые периферийные точки и корректируя радиус и положение новой окружности. Хотя, конечно, окружность проще сразу для квадрата строить. Сейчас подумал, не пойму как её сжимать...

Считаем далее площадь треугольника. Потом процедура повторяется: поворачиваем квадрат (если точки вылезли из него, то увеличиваем его), на основе его -- равносторонний треугольник, уменьшаем треугольник, находим площадь.
После всего узнаём когда была самая минимальная площадь -- треугольник найден.

Почему именно равносторонний? Это вопрос к математикам, пусть докажут.
P.S. Есть способ численного доказательства: набросать случайных треугольников на точки и сжать их все, посчитать площади и сравнить с равносторонним случаем. Чем больше будет выборка, тем "точнее" доказательство.

[maxal]

Вот тут решают эту задачу (и смежные с ней) с дополнительным требованием равнобедренности треугольника: http://www.ams.sunysb.edu/~saurabh/rese ... t-cccg.pdf

Добавлено спустя 5 минут 59 секунд:

Там же дается ссылка на такую статью:

[16] J. O'Rourke, A. Aggarwal, S. Maddila, M. Baldwin. An optimal algorithm for finding minimal enclosing triangles. J. of Algorithms, 7, 1986.
http://dx.doi.org/10.1016/0196-6774(86)90007-6

Цитата:

Klee and Laskowski's $O(n log^2n)$ algorithm for finding all minimal area triangles enclosing a given convex polygon of n vertices is improved to $\Theta(n)$, which is shown to be optimal both for finding all minima and for finding just one.

[saqwer]

Эта же задача стоит и передо мной. У кого-нибудь осталась эта (J. O'Rourke, A. Aggarwal, S. Maddila, M. Baldwin. An optimal algorithm for finding minimal enclosing triangles. J. of Algorithms, 7, 1986. ) статья?
Или может быть знает ссылочку, где можно ее скачать?

[maxal]

saqwer
http://ifolder.ru/15850561

[venco]

Можно показать, что по крайней мере две стороны минимального треугольника совпадают со сторонами выпуклой оболочки. Третья сторона либо тоже совпадает со стороной оболочки, либо однозначно определяется точкой, через которую она проходит. Таким образом можно найти треугольник за $O(m^3)$, где $m$ - количество вершин оболочки.