最接近点对问题-递归与分治策略
最接近点对问题
给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。
为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。
假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。
递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。
能否在线性时间内找到p3,q3？
文件下载
评论信息
其他资源
- UG自动出图
- 16.神经网络机器翻译技术 python代码实现
- Matlab实现的阿拉伯数字识别程序代码
- 某宝TOP20万核心关键词表.xlsx
- 基于java的点餐系统
- excel-快捷键-mac版.docx
- 售前、售中、售后服务方案及保障措施方案
- WPF自定义表格控件
- DPAA 说明文档.pdf
- 基于MATLAB开发平台的继电保护仿真系统
- 生命游戏（源码+可执行jar)
- 树莓派多用户桌面访问.zip
- newstylebutton_for_pb9
- MATLAB 蒙特卡洛
- 格式转换工具.zip
- 动画过渡，帧率靠谱！
- FontCreator中文破解版9.0
- cmake cmake-3.10.0
- EXCEL学习教程完全版
- SniferPro捕包及协议分析
- 最全的点阵字库（ASC12, ASC16, HZK16, HZK24,...）
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明