两凸多边形的最小外接圆

aimisiyou

给定两凸多边形，如何靠接使得两凸多边形整体的最小外接圆半径最小？算法如何求解？

mathe

我们的目标是找一个多项式时间复杂度的算法。

i)首先,外接圆最小时，两个凸多边形必然接触，也就是至少有一个多边形的一个顶点落在另外一个多边形的某条边上（包括边的端点）
ii)外接圆至少过一个多边形的两个顶点和另外一个多边形的一个顶点。

i) 两个多边形的边没有重叠，而是两个多边形仅两个顶点相接触，那么这时这两个多边形都必须至少有两个顶点落在外接圆上（不然，可以将只有一个顶点落在外接圆上多边形保持和另外一个多边形接触但是沿着对方的一条边移动，必然有一种移动方案使得多边形完全移动到圆内部，同最小性矛盾）。
   对于这种情况，我们需要穷举两个多边形中各自选择3个点，让其中各自一个点重叠，然后保持一个多边形不动，转动另外一个多边形使得余下四个点会四点共圆，这现需要解一个代数方程，而且解显然通常只有有限种。穷举复杂度为O(n^6)

ii)同样两个多边形边没有重叠，但是一个多边形A的一个顶点落在另一个多边形B的一条边上，于是这时如果多边形A只有一个顶点落在外界圆上面，那么过这一点的圆的切线必然和多边形B的那条边（A的顶点在其上）平行，不然我们必然可以将A沿着B的这条边向某个方向滑动移动到圆内部。但是这时，我们必然可以将A沿着边向一个方向稍微滑动然后向另外一个方向转动使得多边形保持在圆内部，所以必然不是最优情况，不需要考虑。

iii)同样两个多边形边没有重叠，但是一个多边形A的一个顶点落在另一个多边形B的一条边上，而多边形A有两个顶点在外接圆上，多边形B只有一个顶点在外接圆上，那么B在外接圆上点的切线必须平行和A接触的边，同样可以通过略微滑动和转动到一个更加优秀的方案，所以不需要考虑

iv）同样两个多边形边没有重叠，但是一个多边形A的一个顶点落在另一个多边形B的一条边上，这时A和B都同样至少两个顶点在外接圆上，于是这四个顶点要四点共圆，我们需要穷举包含A的三个顶点和B的两个顶点和一条边的情况共O(n^6)种情况，对于每种情况同样需要解一个复杂的代数方程确定有限组解。

v)两个多边形两条边部分重叠，如果多边形A只有一个顶点落在外接圆上，那么外接圆在这一点处的切线必须和重叠的边平行，于是在选定重叠的边和A上一个额外顶点和B上两个额外顶点，我们就可以解代数方程确定有限组解，这部分复杂度为O(n^5).

后面的问题就是依次对于i), iv), v)三种情况找出对应代数方程求解的算法

aimisiyou

mathe 发表于 2020-1-17 11:37
我们的目标是找一个多项式时间复杂度的算法。

i)首先,外接圆最小时，两个凸多边形必然接触，也就是至少 ...

因为都是凸多边形，整体最小外接圆半径最小时是否一定是边与边重合？有没有仅一点接触时的情况？
此时将重合的边放置于竖直位置，那么可以判断，两凸多边形上都有两点在最小外接圆上。（不然，通过竖向平移导致与最小性矛盾）。

aimisiyou

还有一种情况，该点为左端点（重合边竖直时）。