Найти точку внутри треугольника

[TOTAL]

Грани симплекса в $n$ - мерном пространстве (тетраэдра в $3D$) заданы уравнениями

$$a_{i1}x_1+ a_{i2}x_2+ \cdots + a_{in}x_n+ b_{i}=0, \;\; i=1, \cdots, n+1.$$

Как с наименьшими затратами найти точку (хоть какую-нибудь) внутри симплекса?

[Профессор Снэйп]

1) Берём первые $n$ граней, ищём точку их пересечения.
2) Опускаем из неё перпендикуляр на оставшуюся грань.
3) Выбираем точку внутри отрезка-перпендикуляра.

На первом этапе решается система $n$ линейных уравнений с $n$ неизвестными. На втором --- линейное уравнение. На третьем вообще всё элементарно. Самый затратный по времени --- первый этап. Система, естественно, решается методом Гаусса

[TOTAL]

Профессор Снэйп писал(а):

3) Выбираем точку внутри отрезка-перпендикуляра.

Но этот перпендикуляр может оказаться весь снаружи.

[Профессор Снэйп]

TOTAL писал(а):

Профессор Снэйп писал(а):

3) Выбираем точку внутри отрезка-перпендикуляра.

Но этот перпендикуляр может оказаться весь снаружи.

А... Да, действительно может

[вздымщик Цыпа]

Можно решить все $n+1$ систем, задающие все вершины. Потом взять среднюю точку. Она точно будет внутри.

Добавлено спустя 33 минуты 46 секунд:

А вот интересно, можно ли все эти системы решить «за один проход»? В смысле, чтоб алгоритмические затраты были не сильно больше, чем на решение одной системы.

[TOTAL]

вздымщик Цыпа писал(а):

Можно решить все $n+1$ систем, задающие все вершины. Потом взять среднюю точку. Она точно будет внутри.

В этом способе надо решать много систем уравнений, чтобы получить координаты вершин, которые не нужны.

[вздымщик Цыпа]

Вот-вот, потому я и думаю, нельзя ли их решить одновременно.

Наверное, можно. Ведь поиск обратной матрицы означает вычисление $n^2$ определителей $(n-1)$-го порядка. А тут надо найти $n(n+1)$ таких определителей. Конечно, чтоб найти решение системы, не нужно в явном виде искать обратную матрицу, но все равно наверняка можно соптимизировать и получить метод Гаусса для нескольких «очень похожих» систем.

[Алексей К.]

Пусть треугольник.
Имеется 6 уравнений для 6 неизвестных ($x_1,y_1$), ($x_2,y_2$), ($x_3,y_3$).
Добавляем 2 уравнения и 2 неизв. $3x_0=x_1+x_2+x_3$, $3y_0=y_1+y_2+y_3$.
Итого --- 8+8.
Исключаем ненужные 6, оставляем два нужных.

Типа

$$\left(\begin{array}{cccccccc} a_1& b_1 & 0 & 0 & 0 & 0 & 0 & 0\\ a_2 & b_2\\ 0&&a_2 & b_2\\ 0&&a_3 & b_3\\ 0&&&&a_3 & b_3\\ 0&&&&a_1 & b_1\\ 1& 0&1& 0&1& 0&-3& \hphantom{-}0\\ 0&1& 0&1& 0&1&\hphantom{-}0&-3\end{array}\right) \cdot \left(\begin{array}{c} x_1\\y_1\\x_2\\y_2\\x_3\\y_3\\x_0\\y_0 \end{array}\right)= \left(\begin{array}{c} c_1\\c_2\\c_2\\c_3\\c_3\\c_1\\0\\0 \end{array}\right)$$

Добавлено спустя 31 минуту 23 секунды:

Ну да, вряд и это проще... Если только само решение как-то хорошо выглядит и легко кодируется...

[Профессор Снэйп]

Хм...

Пусть далее $\bar{x}$ означает набор $x_1, \ldots, x_n$.

У нас есть $n+1$ функций

$$ f_i(\bar{x}) = a_{i,1}x_1 + \cdots + a_{i,n}x_n + b_i; \,\, i = 1, \ldots, n+1 $$

Фактически нам надо найти "сигнатуру" внутренних точек, то есть набор $\varepsilon_1, \ldots, \varepsilon_{n+1} \in \{ +, - \}$, такой что для любой точки $\bar{x}_0$, лежащей внутри симплекса,

$$ f_i(\bar{x}_0) > 0 \Leftrightarrow \varepsilon_i = + $$

Может, это как-то можно сделать, не находя самих вершин? Ну или находя не все вершины, а только их часть? Ну а затем уже, имея "сигнатуру", внутреннюю точку мы как-нибудь найдём...

[TOTAL]

Алексей К. писал(а):

Исключаем ненужные 6, оставляем два нужных.
...................
Ну да, вряд и это проще... Если только само решение как-то хорошо выглядит и легко кодируется...

Это проще примерно в два раза, т.к. равносильно тому, что каждая из $n+1$ систем решается методом Гаусса наполовину (только приводится к треугольному виду).

Я написал, что проблема частично решена. Имел в виду, что могу (если не ошибаюсь) найти внутреннюю точку, решив всего одну систему для $n$ неизвестных. Однако коэффициентами этой системы являются скалярные произведения векторов из $n+1$ компонент. Т.е. для получения такой системы требуются вычисления. Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

[ewert]

TOTAL писал(а):

Я написал, что проблема частично решена. Имел в виду, что могу (если не ошибаюсь) найти внутреннюю точку, решив всего одну систему для $n$ неизвестных. Однако коэффициентами этой системы являются скалярные произведения векторов из $n+1$ компонент. Т.е. для получения такой системы требуются вычисления. Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

А практически никак (если я правильно понял ситуацию). Для составления матрицы типа Грама требуется порядка $n^3$ операций, и для последующей реализации метода Гаусса -- тоже.

[TOTAL]

ewert писал(а):

TOTAL писал(а):

Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

А практически никак (если я правильно понял ситуацию). Для составления матрицы типа Грама требуется порядка $n^3$ операций, и для последующей реализации метода Гаусса -- тоже.

Если известна точка внутри тетраэдра, то для каждой грани можно указать (путём подстановки координат этой точки в уравнение грани), по какую сторону от этой грани (положительную или отрицательную) расположен тетраэдр. Можно ли сократить требуемые вычисления, если замахнуться на меньшее (может, оно фактически и не меньшее?), т.е. не искать точку внутри симплекса, а всего лишь определить, по какую сторону от каждой грани он расположен?

Конечной "целью" этой "задачи" является нахождение радиуса и центра вписанного в симплекс шара. Шар вписывается путем решения всего одной системы линейных уравнений, если известна ориентация граней.
Как вписать шар с наименьшими затратами?

[Алексей К.]

TOTAL в сообщении #152410 писал(а):

Шар вписывается путем решения всего одной системы линейных уравнений.
Как вписать шар с наименьшими затратами?

Означает ли данный вопрос "как с наименьшими затратами решить эту всего одну систему линейных уравнений"?

[TOTAL]

Алексей К. писал(а):

TOTAL в сообщении #152410 писал(а):

Шар вписывается путем решения всего одной системы линейных уравнений.
Как вписать шар с наименьшими затратами?

Означает ли данный вопрос "как с наименьшими затратами решить эту всего одну систему линейных уравнений"?

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

[Профессор Снэйп]

Кстати, не будет ли радиус вписанного в симплекс шара наименьшим среди радиусов шаров, касающихся каждой из плоскостей граней симплекса?