精选优质文档-倾情为你奉上基于递归法的最接近点对问题姓名：杨 意学号：9学院：数学信息学院 专业：计算机辅助教育目 录1、 问题综述22、 用递归法解决22.1 一维情形下的分析22.2 二维情形下的分析32.3 算法优化62.4 算法实现63、结论9基于递归法的最接近点对问题摘要：在计算机应用中，常用诸如点、圆等简单的几何对象表现现实世界中的实体。在涉及几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来处理，则具有最大碰撞危险的两架飞机就是这个空间中最近的一点。这类问题是计算机几何学中研究的基本问题之一。本文就运用递归法对一维和二维的情况加以讨论。关键词：最接近点对 递归法问题综述最接近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。实际情况下，最接近点对可能多于一对，为简单起见 ，我们只找其中的一对作为问题的解。有一个最直观的方法就是将每一点与其他
