Минимальный радиус покрытия в n измерениях

Есть ли какой-либо известный алгоритм для решения этой проблемы?Минимальный радиус покрытия в n измерениях

2016-11-01 Guru

Конечно, есть какой-то алгоритм, который вы могли бы использовать. Какую сложность во времени вы пытаетесь достичь? – ollpu

Это требует алгоритма, а не с сломанным кодом – thecoshman

Являются ли центры целыми или целыми, или они могут быть половинками? – m69

Там это родственная проблема, это решаемый с жадным алгоритмом: даны точка и радиуса, найти минимальное количество кругов. Этот алгоритм неоднократно помещает круг, левый край которого лежит в самой левой непокрытой точке, пробегая во времени O (n) в точках, отсортированных по x.

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

источник

2016-11-01 18:21:31

@Blender Он предлагает вам использовать двоичный поиск в ответ, и я согласен с ним. Подобно этим вопросам: [link] (http://stackoverflow.com/questions/40189551/arrange-n-items-in-k-nonempty-groups-such-that- the-difference-between-minimu/40205972 # 40205972) и [link] (http://stackoverflow.com/questions/39673898/divide-array-into-k-contiguos-partitions-such-that-sum-of-maximum-partition-is-m/39675098# 39675098) – Tempux

Минимальный радиус покрытия в n измерениях

ответ

Смежные вопросы