?

Log in

No account? Create an account
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