Пересечение выпуклого многоугольника и движущегося круга

Question

У меня есть прямая линия, которая пересекает выпуклый многоугольник в 2D плоскости. Существует круг с постоянным радиусом. Центр круга движется по этой линии. Поэтому сначала полигон и круг не пересекаются друг с другом, так как круг приближается к многоугольнику, а пересечение увеличивается, а затем уменьшается по мере того, как они идут дальше друг от друга. Я хочу доказать, что площадь пересечения выпуклого многоугольника и окружности не имеет локальных минимумов (так как круг движется по прямой).

Answer 1

Интересная проблема. Пожалуйста, отправьте решение, как только найдете его. Мой подход состоял бы в том, чтобы использовать аналогичный маршрут алгоритму Fortunes для построения графа Вороного - это означает, что я буду рассматривать «события», которые происходят, когда круг пересекает выпуклый многоугольник.

В основном, чтобы лучше понять проблему, рассмотрите ограничение на то, что круг перемещается по прямой линии - почему это важно - посмотрите на примеры счётчиков. Затем посмотрите, когда это произойдет, если поли не выпукло?

События, которые я бы рассмотрел, будут вводом/выводом поли вершины в круг и выходом входа поли края из/в круг. Затем отслеживайте площадь, увеличивающуюся или уменьшающуюся через каждое событие, и показывайте, что она обязательно монотонна.