最近点对算法

、、

所以我正在尝试寻找关于Michael Rabin的算法的细节，该算法在O(n)时间内找到给定2D中的一组点的最近邻居。出于某种原因，谷歌搜索完全让我失望了。我找到的最好的(也是唯一的)描述是：。

浏览 8提问于2011-02-16得票数 5

回答已采纳

2回答

最近点对(线性一维情况)算法

、

我在辅导一个学生，她的作业之一是描述一维情况下最接近的点对的O(nlogn)算法。但限制是她不能使用分而治之的方法。我从几年前一个用户发布的问题中理解了二维情况。然而，对于一维的情况，我只能想到一个解决方案，包括检查直线上的每个点，并将其与其左侧和右侧最近的点进行比较。但是这个解决方案不是O(nlogn)，因为检查每个点将花费与n成比例的时间，并且每个点的比较将花费与2n成比例的时间。如果不使用分而治之的方法，我不确定log(n)从何而来。

浏览 2提问于2014-10-10得票数 1

1回答

如何在使用最近点对算法时存储一对点

、、

我已经实现了一个最近点对算法，我正在尝试找出随机大小的随机点列表中的哪些点是最近的。我没有得到有问题的点，我要么让它再次返回距离，要么什么都不做。我对任何批评都持开放态度，但我对为什么会遇到这些问题感到困惑，因为在理论上，当距离达到新低时，温度表明了这一点，然后我可以将这对点作为变量或在列表中进行附加或设置。

浏览 16提问于2018-01-23得票数 0

回答已采纳

2回答

最近点对算法的一种变种

、

最近的点对问题在计算几何中是众所周知的:给定点(x，y)的列表，找到具有最小欧几里德距离的点对。现在我要问这个问题的一个变体:给定n个点(xi，yi) (n+1>i>0)的列表，找到每个点(xi，yi)的最近欧几里德距离，然后计算所有点的平均最近欧几里德距离。我想知道是否有一些快速算法来解决这个问题。谢谢!

浏览 0提问于2012-07-17得票数 3

回答已采纳

1回答

在O(nlogn)时间内，从n个点集合中得到第一个k个最近点对？

、、、

能不能在一组n个点中找到比快的最近点的k对编辑:参见这里最接近的配对算法：

浏览 4提问于2019-03-04得票数 0

3回答

近似最近对算法

、、、

我一直在考虑的一个变化，其中唯一可用的信息是已经计算出来的距离集(我们不允许根据它们的x坐标对点进行排序)。考虑4个点(A、B、C、D)，以及以下距离：dist(A,C) = 5在本例中，我不需要计算dist(B,C)或dist(A,D)，因为可以保证这些距离大于当前已知的最小距离假设有10个⁸点的集合存在这个问题。这不是课堂上的问题，也不是什么相关的问题。我一直在想这个问题。

浏览 3提问于2013-12-27得票数 3

回答已采纳

2回答

比较两个不同阵列点的最近对算法

、、、、

我想比较一下从一个数组到另一个数组的点，并找到最接近的对。到目前为止，我遇到的都是一个数组。我不想比较来自同一个数组的点。蛮力算法有效，但速度太慢。是否存在使用分而治之方法的算法或实现？编辑1:点被定义为地球表面上的一对(纬度、经度)。

浏览 3提问于2014-08-01得票数 5

回答已采纳

2回答

在ITK中给定一个点，如何得到到边界的径向距离？

我正在加载一个三维CT模型，并对其进行细化算法。现在我想计算一下算法做了多大的细化。如何知道骨架点与其最近/最远边界点之间的距离？

浏览 2提问于2012-05-25得票数 0

1回答

平滑数据而不丢失最近的元素

、

我目前正在尝试实现Savitzky-Golay算法来平滑有噪声的数据。该算法通过选取m相邻元素来平滑每个元素，这意味着最后一个m元素丢失了。最近的元素对我的应用程序非常重要，所以我想保留它们。有没有办法调整算法，使其不丢失最近的元素？或者还有另一种很好的平滑算法可以做到这一点？

浏览 4提问于2015-07-25得票数 0

回答已采纳

1回答

聚类和分裂聚类最终能得到相同的结果吗？

、、、

现在，我知道凝聚是自下而上的方法，而分裂是自上而下的方法。但是，我不知道他们在具体的过程中有什么不同。例如，它们是否都使用邻近矩阵来计算样本之间的任何成对距离？此外，如果设置所有相同的参数，像相同的连接准则，相同的cluster...do目标数，它们最终得到的结果是完全相同的？

浏览 1提问于2021-02-21得票数 1

回答已采纳

4回答

算法，列表元素之间的最近点

、、、、

循环所有这些，但我不知道是否有任何算法可以解决这个问题，我可以使用。尝试了建议的迭代工具解决方案，但当然不是内存问题，而是从几个小时以来一直在运行，它停留在第三个元素上。

浏览 1提问于2018-07-01得票数 5

回答已采纳

1回答

最近邻算法中距离度量的替代方案？

、、、、

我遇到了最近邻居算法的一个实现，用于在两个相似图像中的某些关键点之间查找匹配。关键点由SIFT算法生成。这些点由128维向量描述，并且在两个图像中都有许多这样的点。匹配算法使用最近邻搜索，并且对于一幅图像中的每个点，计算另一幅图像中相应的最近点。“贴近度”由点向量之间的最小欧几里德距离来描述。通过仅采用距离低于特定阈值的那些点对

浏览 2提问于2010-06-30得票数 3

回答已采纳

1回答

数字0-9的二值图像的哪些特征应该与k最近邻算法一起使用？

、

我希望能够使用k最近邻算法对未知集合中的数字进行分类。我已经对算法做了一些研究，我读到最好的方法是取数量特征，在一个以这些特征为轴的特征空间中绘制每个训练数据，对于未知集中的每一幅图像，做同样的事情，使用k最近邻算法找到最近的点，类似于做了什么。

浏览 3提问于2014-03-04得票数 2

回答已采纳

3回答

打印最近的对点

、、

我写这段代码是为了找到我所写的两个points.The代码之间的最小距离，给出了正确的最小距离，但没有给出最小距离是computed.Kindly的正确坐标，帮助我识别问题，根据我的说法，这是打印点以及最小距离的正确方法

浏览 5提问于2015-07-29得票数 0

回答已采纳

2回答

将点与图像上最近的对象配对

、

我有一堆点和它们的坐标。我想分析一个只包含黑色对象的二进制图像-这些对象近似为矩形-并为我的集合中的每个点分配最近的对象。我所知道的是，对于我的集合中的每个点，都有一个物体在它附近，我只是不知道在哪里。我的想法是找到图像上的对象，然后使用最近点对问题的算法之一。一直在寻找一种明显比我前面提到的算法更好的算法，但没有多少运气。

浏览 0提问于2014-09-25得票数 0

1回答

JavaScript中的最近对算法

、、

我试图实现一个分而治之的算法，用JavaScript在一组随机生成的点中找到最近的一对点。该算法应该在O(n log n)时间内运行，但运行时间比简单的蛮力算法( O(n^2) )要长得多。我为16000点的数组创建了两个jsfiddles算法：我的假设是，由于JavaScript数组实际上是哈希表，所以划分和征服是如此缓慢。在JavaScript中是否有可能大大加快算法的速度？如果是这样的话，做这件事最好的方法

浏览 2提问于2012-10-17得票数 8

1回答