Минимальный эллипсоид содержащий точки

[proger256]

Здравствуйте.
Есть конечное множество точек в трехмерном пространстве. Надо найти минимальный осе-выравненный (оси эллипсоида параллельны координатным осям) эллипсод содержащий эти точки.
Минимальность считается по длине максимальной оси эллипсоида. Если в такой форме задача сложна, то можно считать минимальность по объему эллипсоида.

Дано: конечный набор трехмерных точек
Надо найти: центр и размер эллипсоида
Ищется численное решение на компьютере. Допустимо приближенное итерационное решение.

[Brukvalub]

proger256 в сообщении #1107538 писал(а):

Минимальность считается по длине максимальной оси эллипсоида.

Тогда проще решать задачу для шара. Берем, например, всевозможные пары точек и считаем расстояния от середины соединяющего их отрезка до остальных точек. Если все расстояния оказываются не больше половины длины отрезка, то считаем пару "годной", а расстояние между точками пары называем параметром пары. Затем выбираем одну из "годных" пар с наименьшим параметром. Конечно, этот алгоритм не даст лучший из ответов. Например, для трех точек общего положения лучшим ответом будет описанная вокруг треугольника с вершинами в этих точках окружность. Так что можно аналогичным образом перебрать всевозможные тройки точек общего положения...
Подозреваю, что такая задача уже исследовалась и для ее решения можно найти алгоритмы получше предложенного мной.

[Sender]

Проблема только в том, что годных пар может оказаться менее одной...

[DeBill]

Brukvalub в сообщении #1107540 писал(а):

наименьшим параметром.

Или наибольшим - без разницы, потому как у всех годных параметр будет одинаков. Видимо....
Но вот уже для правильного тетраэдра годных пар нет....

[Brukvalub]

DeBill в сообщении #1107544 писал(а):

Но вот уже для правильного тетраэдра годных пар нет....

Согласен, я и сам уже понял недостатки предложенного мной "алгоритма" и, одновременно с критическим комментариями, попытался откорректировать свое предложение. Скажу еще: мой алгоритм можно модифицировать так: просто считать расстояния от середины отрезка до остальных точек, выбирать параметр пары - наибольшее из расстояний для фиксированной середины, а потом брать пару с наименьшим параметром. Но это явно не оптимальный выбор...

[Sender]

Brukvalub в сообщении #1107540 писал(а):

Так что можно аналогичным образом перебрать всевозможные тройки точек общего положения

Думаю, сначала двойки, затем, если подходящих двоек не найдётся, тройки и наконец, за неимением лучшего, четвёрки. Возможно, для начала стоит также оставить только те точки, что принадлежат выпуклой оболочке.

[proger256]

Цитата:

Тогда проще решать задачу для шара.

Хм, отлично. Задача сразу упрощается.

Цитата:

Brukvalub в сообщении #1107540 писал(а):
Возможно, для начала стоит также оставить только те точки, что принадлежат выпуклой оболочке.

да, так можно уменьшить число точек

Я уже примерно представляю решение. Если существует оптимальный шар, то он содержит на поверхности хоть одну точку.
Может быть он должен содержать по крайней мере 4 точки из множества (???? не уверен, надо проверить).
Тогда решение примерно такое: перебираем все четверки точек, берем их описанный шар (а если такой минимальный шар не один?) и ищем минимальных шар среди них.

[Sender]

proger256 в сообщении #1107549 писал(а):

перебираем все четверки точек, берем их описанный шар

Возьмём простой двумерный случай. Пусть имеются 3 точки, образующие треугольник со сторонами 51, 51, 100. Каков, по-вашему, минимальный радиус круга, содержащего эти точки?

[proger256]

Sender
Верно(

Может тогда трехмерный шар должен содержать хотя бы 3 точки?
По известным трем лежащим на сфере точкам, можно вычислить минимальный шар для всех точек.
А потом все перебрать.

Для двумерного случая круг должен содержать хотя бы 2 точки.
Перебираются все пары точек. Центр искомого минимального круга ищется на их серединном перпендикуляре. Радиус вычисляется.
Затем берется самый маленький круг из рассмотренных.
Тут вроде задача решается.

[ET]

proger256 в сообщении #1107553 писал(а):

Sender
Верно.
Может тогда трехмерный шар должен содержать хотя бы 3 точки?

Да две, две, если хотя бы две есть

[Sender]

proger256 в сообщении #1107553 писал(а):

Может тогда трехмерный шар должен содержать хотя бы 3 точки?

Ох, ну возьмите тетраэдр $ABCD$ со сторонами $AB=BC=AD=CD=51$, $AC=100$, $BD=1$.

[ET]

А вот что интересно (ТС вверху упоминал возможность приближенного итеррационного решения)

Пусть есть сферашар, содержащая все точки. И пусть она неоптимальная, то есть допускает дальнейшее уменьшение
Следует ли из этого то, что все точки касания этой сферы с заданными точками лежат в одной полусфере?

[proger256]

Sender
я беру треугольник ABC
беру точку из его плоскости, только не центр описанной окружности, а центр минимального круга содержащего точки A,B,C
провожу из нее перпендикуляр к ABC, на перпендикуляре ищу минимальный шар покрывающий остальные точки (точку D).
Этот шар не обязательно описанный вокруг тетраэдра (например может иметь центр в плоскости ABC)
Повторяю алгоритм для остальных граней и нахожу минимальный шар из полученных.
В принципе аналогично задача решается для 2D для 2 точек.

Цитата:

А вот что интересно (ТС вверху упоминал возможность приближенного итеррационного решения)

Я надеялся, что можно как-то свести задачу к операторам и матрицам с итерационными методами.

Цитата:

Следует ли из этого то, что все точки касания этой сферы с заданными точками лежат в одной полусфере?

Нет, возьмем много точек по всех поверхности сферы.
Они лежат по разные стороны, и минимальный шар для их - эта сфера.

[demolishka]

Предложу такой алгоритм. Строим выпуклую оболочку, берем ёё центр масс и считаем его центром искомого шара. Далее бинарным поиском по радиусу шара находим оптимальный. Сложность $O(N\log N) + O(N \log R),$ где $N$ - количество точек и $R$ - наибольший возможный радиус.

[slavav]

Для поиска минимального шара есть готовое решение. См. https://en.wikipedia.org/wiki/Smallest-circle_problem. Можно поискать алгоритмы по ключевым словам mindisk algorithm. Есть замечательный алгоритм - с ростом размерности пространства он сохраняет линейную сложность в среднем, хотя равномерная сложность $N^{d + 1}$, где $N$ - число точек, $d$ - размерность пространства.
Минимальный осе-ориентированный эллипсоид (и даже минимальный эллипс) куда сложнее. Если ТС устраивают медленные итерации и приближённый результат, то можно устроить поиск минимума в двумерном пространстве. В каждой точке решать mindisk.
В общем ищите "minimal oriented ellipse algorithm".