社区首页 >问答首页 >最近的点对平面情况

问最近的点对平面情况
EN

Stack Overflow用户

提问于 2011-04-24 23:23:11

回答 1查看 1K关注 0票数 0

我正在看维基百科的词条，看看如何解决这个问题。它列出了五个步骤

1.沿x坐标排序点

2.用垂直线x= xmid将点集分割成两个大小相等的子集

3.在左子集中和右子集中递归地解决问题。这将分别给出左侧和右侧的最小距离dLmin和dRmin。

4.求出两点间的最小距离dLRmin，其中一点位于分割线的左边，第二点位于分割线的右边。

5.最终答案是dLmin、dRmin和dLRmin中的最小值。

第四步，我有理解上的困难。如何选择直线左侧的点与直线右侧的点进行比较。我知道我不应该比较所有的点，但我不清楚如何选择要比较的点。请不要给我一个链接，我已经搜索了，去了许多链接，还没有找到一个解释，帮助我理解第四步。

谢谢

Aaron

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2011-04-24 23:39:09

你的问题的答案在维基百科文章的下一段：

结果表明，步骤4可以在线性时间内完成。同样，天真的方法将需要计算所有左右对的距离，即在二次时间内。关键观察值基于点集的以下稀疏性属性。我们已经知道，最近的一对点的距离不会比dist = min(dLmin，dRmin)更远。因此，对于分割线左侧的每个点p，我们必须将距离与分割线右侧的尺寸矩形(dist，2* dist)中的点进行比较，如图所示。更重要的是，这个矩形最多只能包含6个两两距离至少为dRmin的点。步数的递推关系可以写成T(n) = 2T(n / 2) + O( n)，我们可以用主定理来求解，得到O(n )。

我想我不能比他们说得更清楚了，但是你对算法的这一步有什么具体的问题吗？

票数 2

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/5773899

复制

相关文章

java 日志时间错误

java php https 网络安全 html

电脑上所有 java 应用、项目时间都不对。核心业务系统启动后日志时间和当前系统时间差11个小时30分钟，电脑用的是云桌面系统有严格的权限控制，找相关人和同事弄了几次没好；都知道是时区问题，但没注意到系统桌面右下角的提示。最后解决方法很简单，先说解决方法。（出现问题的主机是无法连接公网的，文件也无法外传，图片都是照片；）

全栈程序员站长

2022/07/25

1.6K0

ntp服务器时间(查看服务器时间)

大家好，又见面了，我是你们的朋友全栈君。 public static String getNTPServerDateTime(String NTPTimeServerUrl) { String dateTimeMessage; try { NTPUDPClient timeClient = new NTPUDPClient(); InetAddress timeServerAddress = InetAddress.getByName(NTPTimeServe

全栈程序员站长

2022/07/28

6.3K0

思迅软件出现同步服务器时间错误的解决办法

服务器配置软件同步系统

1、请点击“开始”—“运行”—“gpedit.msc”—“回车”—“打开组策略”。在组策略管理器中选择“计算机配置”— “windows设置”—“安全设置”—“本地策略”—“用户权利指派”—“更改系统时间”。双击打开“更新系统时间配置”属性对话框，在里面“添加用户或组”—“高级”—“查找”—“选择你的用户名”—“确定”； 2、登录服务器查询服务器时间后，修改分部电脑时间与服务器时间一致，前后时间差异不能小于3分钟； 3、操作系统过于精简用户没有自动修改时间权限导致，重新安装分店纯净版电脑操作系

学派客

2023/04/06

1.1K0

自动与时间服务器时间同步,Windows系统时间同步(附时间同步服务器地址)

go windows https java 网络安全

] 分支，并双击 SpecialPollInterval 键值，将对话框中的“基数栏”选择到“十进制”上，如图1所示

全栈程序员站长

2022/09/13

12.3K0

自动与时间服务器时间同步,Windows系统时间同步(附时间同步服务器地址)

如何搭建ntp时间服务器(搭建时间同步服务器)

ntp linux centos java https

NTP（Network Time Protocol，网络时间协议）是用来使网络中的各个计算机时间同步的一种协议。它的用途是把计算机的时钟同步到世界协调时UTC，其精度在局域网内可达0.1ms，在互联网上绝大多数的地方其精度可以达到1-50ms。 NTP服务器就是利用NTP协议提供时间同步服务的。

全栈程序员站长

2022/07/25

15.9K0

NTP时间服务器

ntp node.js tcp/ip

大家好，又见面了，我是你们的朋友全栈君。1. NTP简介 NTP（Network Time Protocol 网络时间协议）是一个用于同步计算机时钟的网络协议。它可以使计算机与其他服务器或时钟源进行时间同步，进行高精度的时间校正。

全栈程序员站长

2022/07/22

5K0

Linux 时间服务器

NTP：Network Time Protocol 网络时间协议，用来同步网络中各主机的时间，在linux系统中早期使用ntp来实现，后来使用chrony来实现，Chrony 应用本身已经有几年了，其是是网络时间协议的 (NTP) 的另一种实现。

星哥玩云

2022/09/15

4.7K0

500-内部服务器错误_显示内部服务器错误怎么办

访问管理 http https java 网络安全

HTTP500内部服务器错误”解决方法 – 苦涩的茶 – 博客园HTTP500内部服务器错误的提示,无法法查看错误的详细信息,用户也没办法根据具体的问题来解决,这对很多新用户确实是一件很麻烦的事情,遇来源：www.mingqicha.com

全栈程序员站长

2022/09/22

3.8K0

NTP时间服务器简介

ntp https udp java 网络安全

NTP(Network Time Protocol) 网络时间协议，工作在UDP的123端口上。是用来使计算机时间同步化的一种协议，它可以使计算机对其服务器或时钟源（如石英钟，GPS等等)做同步化，它可以提供高精准度的时间校正（局域网上与标准间差小于1毫秒，互联网上几十毫秒），且可介由加密确认的方式来防止恶毒的协议攻击。

全栈程序员站长

2022/07/25

2.7K0

Linux NTP时间服务器

linux ntp centos

NTP 时间服务器 ntp也是一种协议 ntp软件（支持ntp协议） CentOS6自带 CentOS7需要安装 chrony软件（支持ntp协议） CentOS7自带安装ntp CentOS6系统自带ntp，CentOS7需要自己安装 [root@m02 ~]# yum -y install ntp [root@m02 ~]# rpm -qa ntp ntp-4.2.6p5-25.el7.centos.2.x86_64 配置ntp 权限参数含义 noquery：不提供ntp服务 notrap：不提

863987322

2018/01/24

8K0

构建NTP时间服务器

NTP服务器是用于局域网服务器时间同步使用的，可以保证局域网所有的服务器与时间服务器的时间保持一致，某些应用对时间实时性要求高的必须统一时间。互联网的时间服务器也有很多，例如ntpdate ntp.fudan.edu.cn 复旦大学的NTP免费提供互联网时间同步。 NTP时间服务器安装： yum install ntp ntpdate -y 即可！修改ntp.conf配置文件 vi /etc/ntp.conf 只修改如下两行，把#号去掉即可！ server 127.127.1.0 # l

程序员同行者

2018/08/16

3.4K0

macbook重设密码服务器错误_网页显示500错误

iis vbscript 命令行工具 java https

1。右键我的电脑–管理–本地用户和组，给IUSR_机器名和IWAM_机器名两个用户设置密码，要一样。

全栈程序员站长

2022/09/21

3.1K0

修改CentOS服务器时间为北京时间

购买了VPS，CentOS系统，发现服务器时间与北京时间往往不一致，存在时差。 [clive@server workspace]$ date 2018年 05月 30日星期三 02:02:47 UTC 可以执行tzselect命令按提示更换时区，依次选择5-Asia，9-China，1-Beijing Time。 Please identify a location so that time zone rules can be set correctly. Please select a continen

Clive

2018/06/08

4.3K0

服务器的时间配置

ntp actionscript yum linux

在crontab -e 中配置自动同步时间：0 /usr/sbin/ntpdate -u ntp.api.bz

@凌晨

2020/05/28

2K0

服务器ntp时间同步

注意：若不加上-u参数，会出现以下提示：no server suitable for synchronization found

summerking

2022/09/19

5.7K0

与时间服务器同步

但可以分如下2种限制： 2.1 只允许192.168.100.0网段的客户机进行时间同步在restrict default kod nomodify notrap nopeer noquery（表示默认拒绝所有IP的时间同步）之后增加一行：

俊才

2019/09/18

4.3K0

Linux服务器时间同步

数据库 mysql 系统硬件

查看系统时间 [root@localhost ~]# date Tue Jun 13 10:20:13 CST 2017 查看硬件时间 [root@localhost ~]# hwclock --show Tue 13 Jun 2017 02:11:12 AM CST -0.848845 seconds 可以看出系统时间比硬件时间快，系统时间是准确的假如系统时间和硬件时间都不准确更新系统年月日 [root@localhost ~]# timedatectl set-time 2018-05-31 更新

咻一咻

2020/05/29

5K0

服务器时间做好啦

做好了农历和公历时间的动态显示。有意思。哈哈。 //后台： $(document).ready(function () { //从服务器上获取初始时间 var currentTime = ''; GetAllDate(currentTime); }); 前台： <span id="Clock"></span> <span id="LunarClock"></span> GetLuna

超级大猪

2019/11/22

1.1K0

NTP时间服务器搭建

惨绿少年

2017/12/27

4.7K0

js获取服务器时间

var DD,MM,YY,hh,mm; if(document.all){ window.XMLHttpRequest=function(){ var get=['Microsoft.XMLHTTP','Msxml2.XMLHTTP']; for(var i=0;i<get.length;i++){try{return new ActiveXObject(get[i])}catch(e){}}; }; } window.time=new Date(); targ

deepcc

2018/05/16

6.5K0

相似问题

PHP ()给出了错误的时间-- CentOS服务器时间

13

Django服务器显示错误的时间

217

服务器上的时间转换错误

17

服务器端日期时间错误

31

Django -服务器上的日期时间错误

121

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例