2014 dxdy logo

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

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


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


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

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

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

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

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



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


23/08/07
4780
Нов-ск
Профессор Снэйп писал(а):
Кстати, не будет ли радиус вписанного в симплекс шара наименьшим среди радиусов шаров, касающихся каждой из плоскостей граней симплекса?
Будет, конечно. Но как это может помочь?

 Профиль  
                  
 
 
Сообщение22.10.2008, 13:31 


29/09/06
4552
Задача на плоскости легко формализуется в нужном Вам направлении, и, полагаю, Вам это проблем не составляет.
TOTAL в сообщении #152457 писал(а):
Так как сначала надо решить, по какую сторону от граней вписывать шар.
А это тот же тупик --- надо правильно ориентировать грани.

(1) Найти координаты одной вершины --- и по ней ориентировать все те грани, к которым она не принадлежит. Найти другую вершину...

(2) Или --- найти точку в $\varepsilon$-окрестности любой вершины, так, чтобы она была "внутри" стерео-угла (по терминологии треугольника --- на луче-биссектрисе внутреннего угла).

Понятно, для чего Вам была нужна хоть какая-то точка внутри... Пока по-прежнему непонятно, как это сделать "быстро".

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


11/05/08
31889
TOTAL писал(а):
Профессор Снэйп писал(а):
Кстати, не будет ли радиус вписанного в симплекс шара наименьшим среди радиусов шаров, касающихся каждой из плоскостей граней симплекса?
Будет, конечно. Но как это может помочь?

если вписанные шары вообще строить уже умеем, то -- тупым перебором пожет. Неэффективно, но работать будет

--------------------------------------------------------------------------
Ну ладно, будем считать это шуткой, а вот такая мысля. Выстраиваем все $(n+1)$ уравнение граней в одну переопределённую систему и приводим её к почти треугольному виду (так, чтобы первая ненулевая диагональ выходила из правого нижнего угла). Это требует порядка $n^3$ операций. Теперь каждая вершина находится выкидыванием одной из строк, а на решение остающейся почти треугольной системы требуется порядка $n^2$ операций. Итого $n^3$ операций на всё про всё, а чего ещё желать?.

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


23/08/07
4780
Нов-ск
ewert писал(а):
TOTAL писал(а):
Профессор Снэйп писал(а):
Кстати, не будет ли радиус вписанного в симплекс шара наименьшим среди радиусов шаров, касающихся каждой из плоскостей граней симплекса?
Будет, конечно. Но как это может помочь?

если вписанные шары вообще строить уже умеем, то -- тупым перебором пожет. Неэффективно, но работать будет.

Очень неэффективно.
Например на плоскости заданы прямые
$4x-3y+9=0$
$12x+5y-43=0$
$7x+24y+19=0$
Для построения всех касающихся этих прямых окружностей надо решить систему уравнений
$|4x-3y+9|/5=|12x+5y-43|/13=|7x+24y+19|/25=R$,
раскрывая разными способами скобки.
Если же известно, что первая и третья прямая ориентированы положительно, а вторая прямая - отрицательно, то решаем всего одну систему уравнений
$(4x-3y+9)/5=-(12x+5y-43)/13=(7x+24y+19)/25=R$
и находим радиус $R=2$ и координаты центра $x=1, \;\; y=1$ именно вписанной в треугольник окружности.

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

ewert писал(а):
Выстраиваем все $(n+1)$ уравнение граней в одну переопределённую систему и приводим её к почти треугольному виду (так, чтобы первая ненулевая диагональ выходила из правого нижнего угла). Это требует порядка $n^3$ операций. Теперь каждая вершина находится выкидыванием одной из строк, а на решение остающейся почти треугольной системы требуется порядка $n^2$ операций. Итого $n^3$ операций на всё про всё, а чего ещё желать?.

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

Как же так получается, что для нахождения хотя бы какой-то точки внутри симплекса требуется столько же оперций как и для нахождения всех вершин? Ведь когда хочешь получить меньше, обычно рассчитываешь, что и платить надо будет меньше.

 Профиль  
                  
 
 
Сообщение22.10.2008, 15:52 


29/09/06
4552
Мы бы вправе рассчитывать, что центр тяжести стоит меньше.
А насчёт любой точки --- не уверен... Эдак Вы подешёвке всю внутренность скупите! :lol:

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


11/05/08
31889
Я, кстати, сжульничал, за что и приношу извинения. Вычеркивать строки из полученной почти треугольной матрицы нельзя -- это уже будут не вершины. Но выкрутиться, кажется, всё-таки можно. Если сохранять левотреугольную матрицу, реализующую прямой ход иетода Гаусса. И вычёркивать строки [i]исходной[\i] матрицы. Тогда матрица, полученная умножением левотреугольной на оставшуяся после вычёркивания, не будет, конечно совпадать с соответствующей частью правой почти треугольной, но отличия не очень велики, и порядок $n^2$ для системы вроде бы остаётся.

А что до того, что "птичек жалко" (пардон, точек) -- то тут, мне кажется, ничего не поделаешь. По отношению к каждой проверяемой точке каждая следующая вершина даёт принципиально новую информацию, так что вряд ли удастся обойтись лишь частью вершин.

 Профиль  
                  
 
 
Сообщение23.10.2008, 00:55 


12/09/08

2262
Не, со сферами плохо. Их вроде бы $2^n$, из которых реализуется $n+2$, причем сразу не скажешь, которые именно. И из них уже правильная только одна.

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

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

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



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

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


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

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