Просьба подсказать, как оценить снизу минимальное значение суммы взаимных расстояний в хемминговом и евклидовом пространствах (указать на источник, если имеется).

1. Сначала суть задачи для пространства Хемминга $% E^n $% (для определенности над троичным алфавитом), $% d_E() $% – .метрика Хемминга.

Пусть $% X \subseteq E^n, x_i \in X, i=1,2,...,N (|X|=N). $% Нужна оценка снизу величины:

$% W(X)= \sum_{i < j} d_E(x_i,x_j) $%

неравенством $% M(n,N) \le \sum_{i < j} d_E(x_i,x_j). $%

Тривиальную оценку легко получить из следующих соображений. Пусть $% x_i $% – любая выбранная точка $% S(x_i,r) $% – шар радиуса $% k $% с центром в $% x_i $% . Сумма расстояний всех других точек от точки $% x_i $% минимальна, если все эти точки находятся внутри шара $% S(x_i,r) $% минимального радиуса $% r, $% Тогда сумма расстояний от точки $% x_i $% всех других точек равна

$$ (1) \;\;\;\;\;\;\;\;\;\; \sum_{i} d_E(x_i,x_j) = \sum_{k = 1}^{r} 2^k k C_n^k - rM, $$

где $% r=r(n,N) $% – минимальное целое число, удовлетворяющее неравенству $$ N \le |S(x_i,r)| = \sum_{k = 0}^r 2^k C_n^k, $$ $% M= |S(x_i,r) |- N. $% Суммируя неравенство (1) по $% x_i, $% получим тривиальную оценку $$ (2) \;\;\;\;\;\;\;\;\;\; W(X) \le N ( \sum_{k = 1}^r 2^k kC_n^k-rM)/2, $$ Грубость оценки (2) обусловлена тем, что расстояния от каждой точки рассчитываются как от центральной. Уточнить оценку можно, подсчитав взаимные расстояния от точек, которые уже помещены в шар $% S(x_i,r). $% Однако для этого нужно: а) иметь основание для такой оценки, т. е. знать, что сумма взаимных расстояний между точками минимальна тогда, когда эти точки находятся внутри шара минимального радиуса (так ли это?), б) получить оценку минимальной суммы взаимных расстояний между точками, находящимися на максимальном удалении от центра шара, указанного в п. а), в) посчитать (оценить) суммы взаимных расстояний от различных точек.

2. Задача для пространства Евклида $% R^n $% формулируется аналогично, однако рассматриваются лишь точки с целочисленными координатами из {-1, 0, 1}, т. е. целочисленные точки в [-1,1]-гиперкубе).

Несмотря на то, что вопросы по пп. б), в) технические, однако также интересно было бы получить предложения. Спасибо.

задан 19 Окт '13 0:29

изменен 19 Окт '13 1:18

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×2,237
×727

задан
19 Окт '13 0:29

показан
367 раз

обновлен
19 Окт '13 1:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru