2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 09:50 


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

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:00 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
proger256 в сообщении #1107538 писал(а):
Минимальность считается по длине максимальной оси эллипсоида.

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:20 


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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:20 
Заслуженный участник


10/01/16
2318
Brukvalub в сообщении #1107540 писал(а):
наименьшим параметром.

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:27 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
DeBill в сообщении #1107544 писал(а):
Но вот уже для правильного тетраэдра годных пар нет....

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:32 


14/01/11
3019
Brukvalub в сообщении #1107540 писал(а):
Так что можно аналогичным образом перебрать всевозможные тройки точек общего положения

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:42 


18/03/16
5
Цитата:
Тогда проще решать задачу для шара.

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

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

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 10:52 


14/01/11
3019
proger256 в сообщении #1107549 писал(а):
перебираем все четверки точек, берем их описанный шар

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 11:08 


18/03/16
5
Sender
Верно(

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

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 11:13 


08/05/08
600
proger256 в сообщении #1107553 писал(а):
Sender
Верно.
Может тогда трехмерный шар должен содержать хотя бы 3 точки?

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 11:16 


14/01/11
3019
proger256 в сообщении #1107553 писал(а):
Может тогда трехмерный шар должен содержать хотя бы 3 точки?

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 11:19 


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

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 11:29 


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

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

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

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

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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 12:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Минимальный эллипсоид содержащий точки
Сообщение18.03.2016, 13:18 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: DariaRychenkova


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group