2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Найти точку внутри треугольника
Сообщение21.10.2008, 11:06 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
Грани симплекса в $n$ - мерном пространстве (тетраэдра в $3D$) заданы уравнениями
$$a_{i1}x_1+ a_{i2}x_2+ \cdots + a_{in}x_n+ b_{i}=0, \;\; i=1, \cdots, n+1.$$
Как с наименьшими затратами найти точку (хоть какую-нибудь) внутри симплекса?

 Профиль  
                  
 
 
Сообщение21.10.2008, 11:19 
Заморожен
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение21.10.2008, 11:56 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
Профессор Снэйп писал(а):
3) Выбираем точку внутри отрезка-перпендикуляра.
Но этот перпендикуляр может оказаться весь снаружи.

 Профиль  
                  
 
 
Сообщение21.10.2008, 12:00 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
TOTAL писал(а):
Профессор Снэйп писал(а):
3) Выбираем точку внутри отрезка-перпендикуляра.
Но этот перпендикуляр может оказаться весь снаружи.


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

 Профиль  
                  
 
 
Сообщение21.10.2008, 12:40 


12/09/08

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

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

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

 Профиль  
                  
 
 
Сообщение21.10.2008, 12:49 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
вздымщик Цыпа писал(а):
Можно решить все $n+1$ систем, задающие все вершины. Потом взять среднюю точку. Она точно будет внутри.
В этом способе надо решать много систем уравнений, чтобы получить координаты вершин, которые не нужны.

 Профиль  
                  
 
 
Сообщение21.10.2008, 12:50 


12/09/08

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

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

 Профиль  
                  
 
 
Сообщение21.10.2008, 13:26 


29/09/06
4552
Пусть треугольник.
Имеется 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 секунды:

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

 Профиль  
                  
 
 
Сообщение21.10.2008, 13:32 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Хм...

Пусть далее $\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 = +
$$

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

 Профиль  
                  
 
 
Сообщение21.10.2008, 14:02 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
Алексей К. писал(а):
Исключаем ненужные 6, оставляем два нужных.
...................
Ну да, вряд и это проще... Если только само решение как-то хорошо выглядит и легко кодируется...

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

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

 Профиль  
                  
 
 
Сообщение21.10.2008, 18:36 
Заслуженный участник


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

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

 Профиль  
                  
 
 
Сообщение22.10.2008, 07:02 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
ewert писал(а):
TOTAL писал(а):
Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

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

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

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

 Профиль  
                  
 
 
Сообщение22.10.2008, 11:36 


29/09/06
4552
TOTAL в сообщении #152410 писал(а):
Шар вписывается путем решения всего одной системы линейных уравнений.
Как вписать шар с наименьшими затратами?

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

 Профиль  
                  
 
 
Сообщение22.10.2008, 12:14 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
Алексей К. писал(а):
TOTAL в сообщении #152410 писал(а):
Шар вписывается путем решения всего одной системы линейных уравнений.
Как вписать шар с наименьшими затратами?

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

 Профиль  
                  
 
 
Сообщение22.10.2008, 12:21 
Заморожен
Аватара пользователя


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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