Вопрос:
На плоскости имеется n точек, как можно приблизительно найти минимальный радиус круга, который покрывает некоторые k из n этих точек? Число n должно быть меньше 10 ^ 4.
много информации по делу k == n в Википедии, но я ничего не нашел в общем случае.
Ответ №1
Здесь алгоритм, который, учитывая радиус r > 0 и константу аппроксимации c > 0, возвращает круг радиуса (1+c) r, охватывающий не менее k точек, или объявляет, что нет круга радиуса r строго охватывающих не менее k точек. Время работы O(n (1 + k^-1 c^-2 log c^-1)), которое при использовании в сочетании с бинарным поиском для получения достаточно грубой оценки должно быть быстрее, чем алгоритм tmyklebu. (Чтобы инициализировать поиск, возможно во время O(n^2) получить 2 -приближение для r путем циклического перехода по точкам и запустить quickselect, чтобы найти k th ближайшую другую точку.)
Разделите точки, поместив точку (x, y) в квадратную ячейку с меткой (floor(x/(2r)), floor(y/(2r))). Каждая окружность радиуса r имеет внутреннюю часть, которая перекрывает не более четырех ящиков. Если существует окружность радиуса r, охватывающая не менее k точек, то существуют i, j такие, что бины (i, j), (i, j+1), (i+1, j), (i+1, j+1) вместе имеют не менее k точек.
Для каждой из этих подзадач поместите каждую участвующую точку (x, y) в ячейку меньшего квадрата, (floor(x/w), floor(y/w)), где w = cr/(3sqrt(1/2)) – достаточно малая ширина. Теперь подготовьте матрицу O(c^-1) by O(c^-1), где каждая запись указывает, сколько точек содержится в соответствующем бункере. Сверните эту матрицу в двух измерениях с нулевой матрицей, обозначающей ячейки, полностью содержащиеся в круге радиуса (1+c)r. Последняя матрица может выглядеть как
01110 11111 11111 11111 01110.
Теперь мы знаем для каждого центра сетки число, которое ограничено тем, сколько точек окружность радиуса r будет содержать и ограничена тем, сколько точек будет содержать круг радиуса (1+c) r.
Ответ №2
Учитывая радиус кандидата r, вы можете найти максимальное количество точек, которые могут содержаться в круге радиуса r, взяв каждую пару (p1, p2) точек и видя, сколько точек содержится в каждом из два круга радиуса r с p1 и p2 на границе.
Зная это, вы можете выполнить двоичный поиск наименьшего r, так что некоторая окружность радиуса r содержит k или больше точек.
Ответ №3
Одна мысль состоит в том, что вы можете взять среднее значение всех точек в центре, а затем увеличить радиус до тех пор, пока не накроете k очков. При довольно однородных дистрибутивах это, вероятно, сделало бы неплохую работу, но не получилось бы для “комковатых” данных. Например, если точки были в двух плотных кластерах, далеких друг от друга, и k было достаточно маленьким, чтобы просто потребовать одного из них, это бы не впечатляюще. Если есть возможность для этого объединения, рассмотрите возможность использования алгоритма кластеризации для определения локальных кластеров, а затем, если один из них содержит достаточное количество точек, используйте алгоритм именно для этого кластера.
