凸多邊形與移動圓的交點

Question

我有一條直線，它與二維平面中的凸多邊形相交。存在一個半徑不變的圓。圓的中心正在這條線上移動。因此，首先多邊形和圓不相交，因爲圓越接近多邊形，交叉點就會增加，然後隨着距離越來越遠而減小。我想證明凸多邊形和圓的交點的面積沒有局部最小值（當圓上的線移動時）。

Answer 1

有趣的問題。一旦找到它，請發佈解決方案。我的方法是採取類似的途徑Fortune算法來建立Voronoi圖 - 這意味着我會考慮當圓穿過凸多邊形時發生的「事件」。

基本上，爲了更好地理解問題，考慮圓的直線傳播限制 - 爲什麼這很重要 - 請看反例。然後看看如果聚合不是凸的，何時會失敗？

我會考慮的事件是多邊形進入/退出圓形，以及從圓形入口退出多邊形。然後通過每個事件跟蹤區域的增加或減少，並顯示它必然是單調的。