Реализация радиальной развертки

Question

Вы указали N точек в 2D-плоскости, мне нужно узнать наименьший радиус круга, который содержит не менее M точек.

подход я использую: -

Я буду делать бинарный поиск по радиусу окружности.

Выберите произвольную точку P из заданного набора. Вращаем круг C с радиусом R, используя P в качестве «оси вращения» (условно, против часовой стрелки), т. Е. Мы удерживаем C в любое время при касании P. Пока C вращается, мы поддерживаем счетчик, чтобы подсчитать количество точек C.

Обратите внимание, что этот счетчик изменяется только тогда, когда какая-либо точка Q входит в область круга C. (или оставляет). Наша цель - разработать алгоритм, который будет увеличивать (или уменьшать) этот счетчик, когда какая-либо другая точка Q ≠ P входит (или оставляет) область C.

Состояние (вращающейся) окружности C может быть описано одним параметром θθ, где (r, θ) - полярные координаты центра круга C, если выбрать P как неподвижную точку полярной системы координат. С этой системой вращение С означает увеличение θ.

Для каждой другой точки Q (≠ P) мы можем фактически вычислить диапазон θ, для которого C покрывает Q. Положим более формально, C охватывает Q всякий раз (iff) θ∈ [α, β].

Таким образом, до этого момента, исходная задача была сведена к:

Что такое оптимальное значение & thetas, что лежит в самом числе [α, β] интервалы?

Уменьшенная проблема может быть решена с помощью довольно стандартного алгоритма O (NlogN). [3] Эта уменьшенная задача должна быть решена N раз (по одной для каждой точки P), следовательно, временной сложностью O (N2logN).

Я могу получить, как сделать этот шаг:

Для каждой другой точке Q (≠ P), мы можем фактически вычислить диапазон & thetas, для которых C охватывает Q. Помещенный более формально, C охватывает Q всякий раз (iff) θ∈ [α, β]. Итак, до этого момента первоначальная проблема была сведена к: . Какое оптимальное значение θ лежит в наибольшем числе интервалов [α, β]?

вы можете предложить, как реализовать эту часть.

Answer 1

Когда Q входит или покидает окружность С (с радиусом R):

• Расстояние между P и центром C является R (потому что она всегда есть); и

• Расстояние между Q и центром C является также R

Так что, если вы рисуете окружность радиуса R вокруг Q, а окружность радиуса R вокруг P. Две точки, в которых они пересекаются, являются центрами C, когда Q входит или уходит.

Пусть ± θ - углы между центрами C и прямой PQ. Если вы это выберете, вы можете легко увидеть, что | PQ |/2R = cos (θ), что позволяет легко находить углы, которые вы ищете.