首页 > 留学知识库

问题: 覆盖问题


已知A,B,C,D是平面上两两距离不超过1的四个点,问半径最小应该多少的圆才能覆盖上述四点。

解答:

已知A,B,C,D是平面上两两距离不超过1的四个点,问半径最小应该多少的圆才能覆盖上述四点。
凸包覆盖问题都是竞赛题。

证明 设A,B,C,D是满足条件的四点,能覆盖它们的圆的半径为R,考虑四点凸包。
(1)若A,B,C,D四点中有一点,设为D在△ABC的内部或边界上,
若△ABC为锐角三角形,则有一角,设∠A≥60°,2R=a/sinA≤1/[√3)/2] ,R≤1/√3,特别地当AB+CA+AB=1时,R=1/√3。比它小的不可能覆盖此点。
若△ABC为钝角三角形或直角三角形,则以最长的边为直角的圆能覆盖此四点,故有R≤1/2<1/√3.
(2)若凸包为四边形,设为凸四边形ABCD。
若有一对对角,∠A,∠C均大于90°,则以BD为直径的圆能覆盖此四点,故有R≤1/2<1/√3.
若上述情况不发生,凸四边形ABCD四个内角必有一个,设为∠D≥90°,则∠B<90°,又∠A,∠C中至少有一个,设为∠A<90°,考察∠ADB,∠ACB两角,不妨设∠ADB>∠ACB,若∠ADB>∠ACB≥90°,以AB为直径的圆可覆盖此四点,故有R≤1/2<1/√3.
若∠ADB>∠ACB,∠ACB<90°,则D点必在锐角△ABC的外接圆圆内或圆周上,该圆半径R≤1/√3。
综上所述, 覆盖平面上两两距离不超过1的任意四点的最小半径R≤1/√3。