楚继光和李旭琳一人骑着一辆自行车迎面而来,楚继光大叫:“小心,小心,你往左拐,我往右拐!”
呵呵,幸好他们骑的是自行车。更进一步,考虑在空中交通控制中,若将飞机作为空间移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小。严格地说,最接近点对可能多于1对。为了简单起见,这里只限于找其中的一对。