二维空间的最接近点对问题-递归算法与分治策略
二维空间的最接近点对问题
下面来考虑二维的情形。
选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。
递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2 ，如图2-9所示。
能否在线性时间内找到p,q？
考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中，如图2-10所示。
由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。
图2-9距离直线l小于d的所有点
图2-10包含q的d×2d矩形R
文件下载
评论信息
其他资源
- 无线传感器网络定位算法代码大全
- Eigen库的简单实用说明
- OpenCV实现同一窗口显示多幅图片
- echartsgl动态线渲染
- 《高级计量经济学及stata应用（第二版）》配套数据.zip
- 均匀设计课件 实例讲解 方法
- 基于汇编语言的简单电子琴程序设计
- sbus协议解析代码
- asp.net网站注册登录功能源码（基于C#）
- 交互式计算机图形学——基于opengl着色器的自顶向下的方法（第六版）包含文件（include文件）
- logstash5.6.1向es导入oracle数据库数据
- 人才招聘数据库设计
- dlib-19.17.zip
- 通过操纵富人俱乐部连接来更改复杂网络中的主题分布
- gcc-gnat-4.8.5-36.el7.x86_64.rpm
- 32_package_1.0.5_rc4.exe.7z
- 锅炉烟气脱硫塔设计计算电子表.xls
- 汇编语言程序设计教程
- jdk11/jdk8开发工具包
- SQLPrompt_7.1.0.144.rar
- mongodb 4.0.3 版本运行包，包括配置文件 mongodb-win32-x86_64-2008plus-ssl-4.0.3
- SecureCRT-8.3.3-chaoxz.com.dmg
- 单片机C51-电子钟1 LCD1602显示 上电正常计时
- 简单的教务管理系统（C#）
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明