Найти вероятность того, что круг со случайным центром в квадрате содержит ровно K точек

Question

Я работаю над проблемой, которая сводится к следующему:

1. Дан квадрат с вершинами в точках (0, 0), (0, 1), (1, 0) и (1, 1).
2. Дано конечное непустое множество K точек (x, y) строго внутри этого квадрата и число 0
3. Найдите вероятность P, что круг с радиусом R и произвольным центром в квадрате (может лежать по бокам) содержит все K точек.

Я думаю, что это геометрическая вероятность, и для вычисления ответа нам нужно разделить общую площадь всех окружностей, содержащих все K точек, на площадь квадрата, которая, очевидно, равна 1.
Пусть K = 1, тогда довольно просто вычислить P, мы берем эту точку и вращаем вокруг нее окружность, чтобы нарисовать окружность с радиусом 2R, которая включает все окружности радиуса R, содержащие эту точку; вырезать части, лежащие за пределами квадрата, и рассчитать площадь того, что осталось.
Если K = 2, то сначала мы проверяем, не превышает ли расстояние между точками 2R, чтобы существовала окружность, содержащая обе точки. Но я не очень понимаю, как рассчитать общую площадь, так как конечная цифра будет 4-листовым цветком, если это имеет смысл. И так далее для больших K ...

Я чувствую, что это может быть простым решением, и удивляюсь, есть ли более элегантное.

Answer 1

Учитывая K точек, диск радиуса R покрывает их, если он покрывает их выпуклую оболочку. Если вы попробуете все положения диска, самые крайние будут такими, что окружность проходит через одну или две вершины корпуса. Если мы рассмотрим все позиции через данную вершину, мы можем повернуть диск на угол между контактами с двумя соседними вершинами на корпусе. Во время этого вращения центр круга описывает дугу окружности радиуса R.

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

На рисунке выпуклая оболочка с K = 6 точками зеленого цвета. Красные круги - крайние позиции с двумя контактами. Локус центра диска выделен синим цветом.

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

Но отсечение внутри квадрата блока вызовет боль в шее.