Точка сферы, не входящая в множество других точек этой сферы

[hazzo]

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

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

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

Спасибо.

[demolishka]

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

[gris]

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

[hazzo]

demolishka в сообщении #925084 писал(а):

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

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

-- 01.11.2014, 18:05 --

gris в сообщении #925087 писал(а):

Если надо найти точку на гиперсфере, которая просто не совпадает ни с одной имеющихся...

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

gris в сообщении #925087 писал(а):

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

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

[gris]

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

[hazzo]

gris в сообщении #925122 писал(а):

Но Вы всё-таки уточните, как задаётся множество точек и что означает "не совпадение".

Для каждой известной точки, указываются ее вещественные координаты, т.е. $X=(x_1,x_2,...,x_n) \in \mathbb R^n$.
Две точки не совпадают, если они отличаются хотя бы по одной какой-то координате.

gris в сообщении #925122 писал(а):

Предполагается написать алгоритм?

В итоге Да.

[gris]

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

[hazzo]

gris в сообщении #925426 писал(а):

Так в том и дело, как задаются эти координаты? Если в виде конечного массива, то я предлагал алгоритм. При реализации надо отследить только случай ровно одного значения первой координаты.

Ваш метод как мне кажется - частный случае диагонализации. Диагонализация в общем случае не работает. А что получим этим методом если нет на сфере неизвестных нам точек?

gris в сообщении #925426 писал(а):

Или же координаты могут быть заданы уравнениями, неравенствами и т.п.

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

[ИСН]

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

[hazzo]

ИСН в сообщении #925441 писал(а):

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

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

[demolishka]

hazzo в сообщении #925445 писал(а):

Задача четко сформулирована.

В вашей формулировке

hazzo в сообщении #925420 писал(а):

Для каждой известной точки, указываются ее вещественные координаты, т.е. $X=(x_1,x_2,...,x_n) \in \mathbb R^n$.

С учетом

hazzo в сообщении #925095 писал(а):

gris в сообщении #925087 писал(а):

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

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

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

[gris]

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

[demolishka]

gris в сообщении #925469 писал(а):

Кстати, мы же программу пишем, так что с компьютерной точки зрения на сфере конечное число точек И массив точек вполне может заполнять $99.5\%$ её (слова "почти всю" здесь как-то не того).

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

[gris]

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

[hazzo]

demolishka в сообщении #925463 писал(а):

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

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

-- 02.11.2014, 19:19 --

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