Previous Entry Share Next Entry
Задачка по математике
Слон
yashunsky
Уже могу её сформулировать, но пока не способен даже начать думать над решением. Может кто помочь сможет:
Как определить, является ли объединение k n-мерных сфер односвязным?
UPD: скорее даже не односвязным, а изоморфным сфере без ручек.

  • 1
Я бы сформулировал для n=2 для простоты, потом попробовал расширить доказательство по индукции. Не факт, что получится, но вдруг?

у меня типовое значение n=18 :) так что с индукцией должно сильно повезти.
На практике думаю что скорее ограничу k в районе 3-5 и буду проверять просто чтобы не получалось обособленнх групп, а образование внутренних полостей в рамках имеющейся задачи, при таком количестве маловероятно

А сферы у тебя как заданы? Координаты центра и радиус? И как задаётся изоморфизм? Две сферы, соприкасающиеся ровно в одной точке, изоморфны сфере без ручек? А три сферы, соприкасающиеся попарно ровно в одной точке?

Edited at 2013-08-20 12:48 pm (UTC)

да. Центр и радиус. Две сферы, я бы сказал, что изоморфны (у меня всегда есть возможночть увеличить радиус на эпсилон), три - уже изоморфны сфере с ручкой.
Собтсвенно, задача более высокого уровня звучит так: есть множестов точек в n-мерном пространсвте, которое надо охватить поверхностью.
Сейчас я их охватываю сферой, что проще всего, но может давать очень много лишнего. Есть идея сначала кластеризовать точки по k-средним, а уже потом каждый кластер охватывать сферой. Но здесь, очевидно, что можно потерять связность, например, в пределе, если k станет равным числу точек.

Да, в таком виде задача намного понятней =) Ещё подумаю...

А задание плоскости набором сфер - это критичный параметр? Или ты можешь сформировать любую плоскость? Смотри, что у меня получается:
1) Выбираем произвольный параметр d, заведомо меньший половины расстояния между любыми двумя точками.
2) Рисуем вокруг каждой точки сферу радиусом d.
3) Сортируем точки в естественном порядке (например, сначала по 1-й координате, потом по 2-й, и тд.).
4) Рисуем цилиндры радиуса d, соединяя точки по порядку.

Получаем несамопересекающуюся колбасу, объём которой прямо пропорционален d^n, так что его можно сделать сколь угодно маленьким. Если цилиндрами задавать нельзя, можно каждый цилиндр представить как объединение сфер радиуса d, расположенных вдоль оси цилиндра с шагом 2*d - epsilon.

Edited at 2013-08-20 11:13 pm (UTC)

Цилиндр — плохой вариант: мне потом в реальном времени надо считать попадание точки в построенную область. А n-мерный цилиндр я даже представить с трудом могу, не то что обсчитать.
Давать сферу каждой точке — это слишком расточительно. У меня их уже сейчас больше 400, при этом они в основном лежат достаточно плотной группой.

Кластеризуй. потом соединяй колбасой - так проще будет? Или тогда сферы будут пересекаться?

да на пересечение пофиг, я потом все равно дизъюнкцию делать буду. Мне цилиндр не нравится тем, что расчет попаданий в него - это матрица перехода, которую надо хранить.

Смотри. Берем новую точку. Находим для неё индекс n в отсортированном массиве, куда её надо вставить. При d => 0 попадание в цилиндр можно свести к попаданию этой точки на прямую между точками [n-1] и [n+1] с точностью до d. И ничего хранить не надо, и считается быстро.

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

Ладно, как посчитать попадание в цилиндр я понял, но все равно муторно.

Très impressionnant. Ca me fait penser au Transperceneige et sa version en film, Snowpiercer :
(http://www.allocine.fr/film/fichefilm_gen_cfilm=123530.html)

  • 1
?

Log in

No account? Create an account