Задачка по.. эммм.. не знаю чему.

coteico

Есть ограниченная область в N4. Есть ли какие-то более менее хорошие способы определять, сколькими шарами фиксированного радиуса ее можно покрыть? А в N3/N2 ?

seregaohota

N - натуральные числа? Шары замкнуты? Область хорошая? Если область произвольная, то нет. Строим такую область иголку, в которой точки целочисленной сетки встречаются за километр друг от друга
Или надо покрыть только точки решётки, принадлежащие области, а не саму область.
Для шаров r<1 просто число точек сетки тогда :)
Похоже комбинаторная геометрия или типа того. Рыбников рассказывал как он дверью хлопнул на одном семинаре в Париже, когда они стали разбирать задачу о минимальном покрытии круга большого радиуса меньшими кругами интерпретируя это как ядерную атаку на Москву.

seregaohota

а вообще подсчитывают же как-то количество шаров в кодах типа Хемминга, исправляющих ошибки

griz_a

Или надо покрыть только точки решётки, принадлежащие области, а не саму область.

Область в \mathbb{N}^4 это и есть набор точек решетки.

seregaohota

ну да, я в терминах R думал

coteico

Область - совершенно рандомной конфигурации шары - пофигу, считай что радиус такой, что можно разместить так, чтобы интересующая точка - попала в шар - мы в N4, а не R4.
То что существуют случаи когда число шаров равно числу точек - очевидно, как очевидно и то, что не будет решения как функции от только n - числа точек.
Нужны какие-то алгоритмические подходы, как уменьшить количество этих шаров для заданной области.

toxin

Это задача о покрытии (set cover). Она является NP-полной, но есть эвристические алгоритмы. Не думаю, что ограничение шарами сильно поможет и сделает задачу не NP-полной.
Оставить комментарий
Имя или ник:
Комментарий: