找回密码
 欢迎注册
查看: 7095|回复: 3

[讨论] 两凸多边形的最小外接圆

[复制链接]
发表于 2020-1-17 09:41:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
给定两凸多边形,如何靠接使得两凸多边形整体的最小外接圆半径最小?算法如何求解?
-25eacec2bc97c941.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-1-17 11:37:38 | 显示全部楼层
我们的目标是找一个多项式时间复杂度的算法。

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)三种情况找出对应代数方程求解的算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-1-17 12:51:07 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-1-17 12:59 编辑
mathe 发表于 2020-1-17 11:37
我们的目标是找一个多项式时间复杂度的算法。

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


因为都是凸多边形,整体最小外接圆半径最小时是否一定是边与边重合?有没有仅一点接触时的情况?
此时将重合的边放置于竖直位置,那么可以判断,两凸多边形上都有两点在最小外接圆上。(不然,通过竖向平移导致与最小性矛盾)。
57e20b73d61bdd8c.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-1-17 14:07:10 来自手机 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-1-17 14:09 编辑

还有一种情况,该点为左端点(重合边竖直时)。
21b9877682ed6239.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 22:59 , Processed in 0.047520 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表