2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Точка сферы, не входящая в множество других точек этой сферы
Сообщение01.11.2014, 15:28 


22/08/12
127
Здравствуйте всем!
Дана гиперсфера $(O,R)$, а также дан набор точек их декартовыми координатами на этой гиперсфере. Требуется найти точку гиперсферы, не совпадающая ни с одной из известных точек.

Я пытаюсь решить следующим образом.
1) Перейти к сферической системе координат,
2) Определить уравнения больших и малых кругов, на которых находятся известные точки. Для этого использую формулы $(x,n)=0$ для большого круга и $(x,n)=cos(\alpha)$ для малого круга. x-точка на круге, а n - нормаль к плоскости этого круга.
3) далее пока мне не понятно смоделировать другой круг, отличный от известных и на нем получить новую точку или как-то ещё.

Вообще, правильно ли этот подход или есть по проще и более правильный?
Что почитать по поводу этого? Перерыл все мне известные книги по сферической геометрии, но пока результат не получен.

Спасибо.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение01.11.2014, 15:49 
Заслуженный участник
Аватара пользователя


28/04/14
968
спб
Если вы сгенерируете случайную точку на сфере, какова вероятность, что она совпадет с данными в наборе?

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение01.11.2014, 15:58 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Что означает — несовпадающая? Если надо найти точку на гиперсфере, которая просто не совпадает ни с одной имеющихся, то зачем такие сложности? Точек конечное число? Отсортировать их по произвольной координате, взять по этой координате новое значение и добить его какой-то другой произвольной ненулевой координатой.
Другое дело, если на гиперсфере ваш набор представляет собой замысловатые бесконечные или даже континуальные множества точек. Это даже и на прямой будет трудной задачей. А если множество заполняет почти всю гиперсферу, то, боюсь, и случайный выбор точки не поможет.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение01.11.2014, 16:48 


22/08/12
127
demolishka в сообщении #925084 писал(а):
Если вы сгенерируете случайную точку на сфере, какова вероятность, что она совпадет с данными в наборе?

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

-- 01.11.2014, 18:05 --

gris в сообщении #925087 писал(а):
Если надо найти точку на гиперсфере, которая просто не совпадает ни с одной имеющихся...

именно это и надо

gris в сообщении #925087 писал(а):
А если множество заполняет почти всю гиперсферу, то, боюсь, и случайный выбор точки не поможет.

В этом то и проблема.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение01.11.2014, 18:38 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Я совсем недавно сталкивался с подобной задачей. Вокруг сферы расположено несколько сфер различных диаметров. Требуется найти конус из центра сферы с заданным углом при вершине, не задевающий окружающих сфер. Сводится с круглым пятнам на сфере и поиску кружочка заданного размера на пустом месте. А совсем давно я сам писал участок программи, когда для отрезка задаётся массив подотрезков, и тоже надо найти пустой кусочек. Ну это просто, а со сферой, конечно, посложнее. Я думаю, что алгоритмы решения подобных задач уже достаточно разобраны где-нибудь.
Если, конечно, Ваша задача относится к таковым. Но Вы всё-таки уточните, как задаётся множество точек и что означает "не совпадение". Мне кажется, что Вы хотите, чтобы точка была изолирована от остальных вместе с некоторой окрестностью? Уточните, пожалуйста, постановку задачи. Предполагается написать алгоритм?

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 14:50 


22/08/12
127
gris в сообщении #925122 писал(а):
Но Вы всё-таки уточните, как задаётся множество точек и что означает "не совпадение".
Для каждой известной точки, указываются ее вещественные координаты, т.е. $X=(x_1,x_2,...,x_n) \in \mathbb R^n$.
Две точки не совпадают, если они отличаются хотя бы по одной какой-то координате.
gris в сообщении #925122 писал(а):
Предполагается написать алгоритм?

В итоге Да.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 15:03 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Так в том и дело, как задаются эти координаты? Если в виде конечного массива, то я предлагал алгоритм. При реализации надо отследить только случай ровно одного значения первой координаты. (Хотя и он может не сработать, учитывая представление чисел в компьютере).
Или же координаты могут быть заданы уравнениями, неравенствами и т.п. :?:

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 15:40 


22/08/12
127
gris в сообщении #925426 писал(а):
Так в том и дело, как задаются эти координаты? Если в виде конечного массива, то я предлагал алгоритм. При реализации надо отследить только случай ровно одного значения первой координаты.
Ваш метод как мне кажется - частный случае диагонализации. Диагонализация в общем случае не работает. А что получим этим методом если нет на сфере неизвестных нам точек?
gris в сообщении #925426 писал(а):
Или же координаты могут быть заданы уравнениями, неравенствами и т.п. :?:

Могут, но это будущее.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 16:47 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
hazzo, Вы решаете какую-то задачу, о формулировке которой мы не имеем ни малейшего представления, а нам говорите другую, абсурдную. Если точек конечное число, то достаточно взять случайную точку на сфере - и она почти наверняка с ними не совпадёт; если хотите без "почти", то можно проверить и в случае совпадения взять другую случайную точку, и т.д.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 16:52 


22/08/12
127
ИСН в сообщении #925441 писал(а):
hazzo, Вы решаете какую-то задачу, о формулировке которой мы не имеем ни малейшего представления, а нам говорите другую, абсурдную. Если точек конечное число, то достаточно взять случайную точку на сфере - и она почти наверняка с ними не совпадёт; если хотите без "почти", то можно проверить и в случае совпадения взять другую случайную точку, и т.д.

Задача четко сформулирована. Если у Вас есть предложения, то пожалуйста. Не хочу методом тыка.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 17:30 
Заслуженный участник
Аватара пользователя


28/04/14
968
спб
hazzo в сообщении #925445 писал(а):
Задача четко сформулирована.

:D
В вашей формулировке
hazzo в сообщении #925420 писал(а):
Для каждой известной точки, указываются ее вещественные координаты, т.е. $X=(x_1,x_2,...,x_n) \in \mathbb R^n$.

С учетом
hazzo в сообщении #925095 писал(а):
gris в сообщении #925087 писал(а):
А если множество заполняет почти всю гиперсферу, то, боюсь, и случайный выбор точки не поможет.

В этом то и проблема.

Предлагаю следующий алгоритм :D :
1. Если множество заданных точек совпадает со сферой, то искомой точки нет.
2. Иначе перебором всех точек на сфере находим заданную.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 17:50 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Легко сказать — взять случайную точку на гиперсфере. А в алгоритмусе это будет изрядный кусок ненужного текста.
Кстати, мы же программу пишем, так что с компьютерной точки зрения на сфере конечное число точек :-) И массив точек вполне может заполнять $99.5\%$ её (слова "почти всю" здесь как-то не того).

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 17:59 
Заслуженный участник
Аватара пользователя


28/04/14
968
спб
gris в сообщении #925469 писал(а):
Кстати, мы же программу пишем, так что с компьютерной точки зрения на сфере конечное число точек :-) И массив точек вполне может заполнять $99.5\%$ её (слова "почти всю" здесь как-то не того).

Если мы смогли обработать $99.5\%$ точек сферы, то что нам мешает обработать еще $0.5\%$ и решить задачу.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 18:05 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Заданные точки уже даны нам. Мы верим, что они лежат на сфере. А где мы будем брать ещё точки, принадлежащие сфере? У нас же нет полного массива их.

 Профиль  
                  
 
 Re: Точка сферы, не входящая в множество других точек этой сферы
Сообщение02.11.2014, 18:18 


22/08/12
127
demolishka в сообщении #925463 писал(а):
Предлагаю следующий алгоритм :D :
1. Если множество заданных точек совпадает со сферой, то искомой точки нет.
2. Иначе перебором всех точек на сфере находим заданную.

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

-- 02.11.2014, 19:19 --

А что если поступить так:
1) составить систему неравенств из условий, что расстояния между искомой точкой и каждой из известных не равны нулю.
2) решить эту систему.
При этом полученное решение должно удовлетворять уравнению сферы.

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

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



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

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


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

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