试题详情
简答题在最接近点对问题中，用一条垂直线L：x=m将平面点集分为大致相等的两个子集S1和S2。设P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域，d1和d2分别是S1和S2中最小距离，且设d=min{d1，d2}。对于P1中任意一个点p，可能和在P2中点q构成全平面点集的最接近点对的候选点对，请证明：P2中最多有6对这样的候选点对。
  • 根据鸽笼原理：如果n+1只鸽子飞入n个笼子中，那么至少有一个笼子里包含两只或两只以上的鸽子。
    将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个（d/2）×（2d/3）的矩形（如下图a所示）。若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个（d/2）×（2d/3）的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则：

    distance（u，v）≤5d/6

  • 关注下方微信公众号，在线模考后查看

热门试题