Уже могу её сформулировать, но пока не способен даже начать думать над решением. Может кто помочь сможет:
Как определить, является ли объединение k n-мерных сфер односвязным?
UPD: скорее даже не односвязным, а изоморфным сфере без ручек.
yashunskyigor_safonov
На практике думаю что скорее ограничу 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)
Давать сферу каждой точке — это слишком расточительно. У меня их уже сейчас больше 400, при этом они в основном лежат достаточно плотной группой.
PS Я когда ограничил d как половину расстояния между любыми двумя точками, немного ошибся. Для строгого доказательства надо брать d строго меньше половины расстояния между любыми двумя точками по каждой координате (за исключением тех точек, у которых эта координата совпадает).
(http://www.allocine.fr/film/fichefilm_gen_cfilm=123530.html)