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

У меня следующая геометрическая проблема: Вам дан круг с центром в начале координат - 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.

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

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

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

6
задан ZLMN 1 May 2011 в 17:31
поделиться