Поиск тетраэдра максимальной размерности

[Enigne]

Есть такая задача:
дан список точек в n-мерном пространстве. Найти среди них набор вершин тетраэдра, такой, что размерность этого тетраэдра будет максимально возможной.

Мой вопрос в том, будет ли правильным следующий алгоритм, и можно ли найти что-то проще:
1) берем две произвольные не совпадающие друг с другом точки. У нас получился одномерный тетраэдр.
2) если размерность нашего тетраэдра равна размерности пространства n, то останавливаемся.
3) затем выбираем из списка оставшихся точек одну точку A. Если ранг матрицы, составленной из векторов AX (где X одна из точек имеющегося тетраэдра) будет больше текущей размерности тетраэдра, то добавляем точку A к тетраэдру, в противном случае выкидываем её из списка оставшихся точек.
4) Если еще остались потенциальные точки-вершины, то переходим к пункту 2.

Спасибо.

[мат-ламер]

Цитата:

где X одна из точек имеющегося тетраэдра

. Может все точки имеющегося тетраэдра?

[Enigne]

мат-ламер в сообщении #224530 писал(а):

Цитата:

где X одна из точек имеющегося тетраэдра

. Может все точки имеющегося тетраэдра?

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

[мат-ламер]

Извиняюсь, неправильно понял условие. Вроде всё верно.

-- Ср июн 24, 2009 17:50:20 --

А обосновать это можно так. Размерность текущего симплекса на 1 меньше количества точек в нём, а размерность матрицы, составленной из векторов АХ либо равна количеству точек (в этом случае размерность нового расширенного симплекса увеличивается на 1), либо меньше этого количества ( в этом случае точка отвергается). И если на текущем шаге отвергаются все точки, значит они находятся в аффинной оболочке симплекса.

[Enigne]

Все-таки где-то в моём алгоритме ошибка.
На таком наборе точек в семимерном пространстве применение алгоритма к самому списку и к нему же перевёрнутому даёт фигуры разной размерности
(3,4,0,2,1,2,1)
(2,4,1,1,2,2,1)
(2,1,3,4,2,0,1)
(2,2,4,2,0,2,1)
(2,1,4,3,2,1,0)
(2,1,4,3,2,0,1)
(2,1,4,2,2,2,0)
(2,1,3,4,2,1,0)

[ИСН]

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

[Sonic86]

Так, у Вас есть $k$ точек (ну или векторов), из которых возможно построить $2^k$ множеств точек Каждый симплекс, ну или тетраэдр, взаимно однозначно определяется множеством точек. Множества точек буде обозначать буквами $M$ с индексами. Под словом "симплекс" ниже будем понимать невырожденный симплекс, то есть для которого множество точек $M$ линейно независимо. Теперь, если $M_1 \subset M_2$ и $M_2$ - симплекс, то $M_1$ - симплекс. И наоборот: если $M_1$ - не симплекс, то и $M_2$ - не симплекс (Образно выражаясь, у Вас структура этих множеств - это кусок снизу булеана k-элементого множества). Тогда Вам надо найти среди этих всех $M$ максимальные множества, причем максимальной мощности, либо мощности, не меньшей $n$ (вроде как $n$ нужна только здесь, больше нигде). Для каждого множества $M$ у нас есть способ определить, является ли оно симплексом - проверить линейную независимость векторов по матрице. Остается организовать оптимальный перебор всех (ну или некоторых) $M$.
Есть такая аналогия: рассматривать каждую точку как вершину графа $G$ мощности $k$, и будем считать, что любая пара вершин множества $M$ соединена ребром тогда и только тогда, когда $M$ - симплекс. Тогда получится, что Вы ищете в графе $G$ клику максимальной мощности или мощности не меньшей $n$, что, как известно, NP- полная задача. Но это только аналогия, так как в графе если $y$ связано с $x_1,...,x_r$ и $\{x_1,...,x_r\}$ - клика, то $\{x_1,...,x_r,y\}$ - клика, а у нас, если $M$ - симплекс, то для $M \cup {y}$ надо проверять матрицу на линейную зависимость и оттуда находить - симплекс ли $M \cup \{y\}$ или нет.
То, что Вы делаете - вариант случайного поиска симплекса, если случайный поиск устраивает, то можете возможное количество раз строить симплексы $\{x_1\}, \{x_1, x_2\},...$ до тех пор, пока не наткнетесь на максимальный, а затем среди множества получившихся выбрать максимальный.
Можно жадный алгоритм + точный перебор. Ищите хоть какой-то максимальный симплекс по Вашей схеме (можно найти несколько и выбрать симплекс максимальной мощности). Пусть его мощность $m$, тогда осуществляете перебор всех $m+1$-элементных множеств, среди них отбираете симплексы, потом пробуете их укрупнять на один элемент, среди укрупненных тоже отбираете симплексы и т.д. до конца, пока их не останется ни одного.
В общем, трудная задача. Я не думаю, что какая-то еще связь может быть между этими множествами, кроме описанной выше, поэтому придется перебирать кусок булеана снизу.