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

Question

У меня есть следующая геометрическая проблема: Вам дан круг с центром в начале координат - C (0, 0) и радиусом 1. Внутри круга даны N точек, которые представляют центры N различных кругов.Вам предлагается найти минимальный радиус маленьких кругов (радиус всех кругов равен), чтобы покрыть всю границу большого круга.

Количество кругов: 3 ≤ N ≤10000, и проблема должна быть решена с точностью до десятичных дробей P, где 1 ≤ P ≤ 6.

Например:
N = 3 и P = 4

и координаты:
(0,193, 0,722)
(-0,158, -0,438)
(-0,068, 0,00)

Радиус маленьких кружков: 1,0686.

Iесть следующая идея, но моя проблема заключается в ее реализации.Идея состоит в бинарном поиске, чтобы найти радиус, и для каждого значения, заданного бинарным поиском, попытаться найти все точки пересечения между маленькими кружками и большими.Каждое пересечение будет иметь в результате дугу.Следующим шагом является «проецирование» координат дуг на ось X и ось Y, в результате получается ряд интервалов.Если при воссоединении интервалов от оси X и Y в результате получается интервал [-1, 1] на каждой оси, это означает, что весь круг покрыт.

Чтобы избежать проблем с точностью, я подумал о поиске между 0 и 2 × 10 ^P , а также о том, чтобы радиус был равен 10 ^P , что исключало цифры послезапятая, но моя проблема в том, чтобы выяснить, как смоделировать пересечение окружностей, а затем узнать, образует ли воссоединение результирующих интервалов интервал [-1, 1].

Любые предложения приветствуются!

Answer 1

Каждая точка в вашем наборе должна покрывать пересечение своей ячейки на диаграмме вороного набора точек и тест-круг вокруг начала координат.

Чтобы найти радиус, начните с вычисления диаграмма Вороного вашего набора точек.Теперь "закройте" эту диаграмму вороного, пересекая все бесконечные ребра с вашим кругом-мишенью.Затем для каждой точки в вашем наборе проверьте расстояние до всех точек своей «замкнутой» вороной ячейки.Максимум должен быть вашим решением.

Не должно иметь значения, что ячейки замыкаются дугой, а не прямой линией на тестовой окружности, пока радиус вашего решения не станет больше 1 (потому что тогда «маленький»"круги будут сильнее).В этом случае вам также необходимо проверить самую дальнюю точку от центра ячейки до этой дуги.

Answer 2

Я могу что-то упустить, но, похоже, вам нужно только найти максимальное минимальное расстояние между точкой в ​​окружности и заданными точками.

То есть, если вы рассматриваете множество всех точекна круге, и взять минимальное расстояние между каждой точкой до одной из заданных точек, а затем взять максимальные значения всех этих - вы нашли свой радиус.

Это, конечно, не алгоритм, поскольку существует бесчисленное множество точек.

Я думаю, что я буду делать по линии:

1. Найти минимальное расстояние между окружностью и набором точек,это ваш начальный радиус R.
2. Проверьте, был ли покрыт весь круг, например, так: Для любых двух точек, расстояние между которыми превышает 2R, проверьте, был ли покрыт весь сегмент (для каждой точки,проверьте, пересекается ли круг вокруг него, и если да, удалите этот сегмент и продолжайте движение.Это должно занять около o (N ^ 3) (вы перебираете все точки для каждой пары точек).Если я прав (хотя формально я этого не доказал), круг накрывается, если все сегменты покрыты.
3. Из всех сегментов, которые не были покрыты, возьмите длинный и добавьтеполовина его длины до R.
4. Repeat.

Этот алгоритм никогда не покроет круг как таковой, но легко доказать, что он экспоненциально сходится к полному покрытию, поэтому он долженбыть в состоянии найти необходимый радиус с произвольной точностью в пределах разумного количества итераций.

Надеюсь, это поможет.