问题标签 [closest-points]

所以，如果给定两个点 A(x1,y1) 和 B(x2,y2)，如果 x1 <= x2 和 y1<= y2，那么我们说 B 支配 A。现在，给定很多点，我希望找出所有非支配点。简单的方法是将每个点与其他点进行比较并获得所有非支配点。但它是 O(n^2)。所以我尝试了分而治之，非常简单，我可以在 O(nlogn) 中找到它。我们的教授说，它仍然可以在 O(n) 内完成。我觉得这真的不可能。我不是要你为我解决这个问题，而是想知道是否有任何“明显”的方式可以确定在任何条件下都不能在 O(n) 中完成？但是，如果确实有可能，请不要回答，也许可以提供一些线索。

给定两个（低维，可能是二维的）单纯复形 P 和 Q，是否有一种有效的算法来构造 P'，P 的子集由 P 中的所有点组成，这些点与 Q 中的某个点 q 最接近？

例如，如果 P 和 Q 是非退化相交线段，则 P' 将是它们的交点；如果它们不相交，则 P' 将是一个点或段。如果 P 是线段而 Q 是三角形，则 P' 将是 Q 到 P 上的投影。如果 P 是三角形并且 Q 是与 P 相交的线，则 P' 将由多个入射线段组成，从内部和/或三角形的外部。

一些图片示例：（带有点相交的那个是不正确的）

一般来说，P' 似乎由 Q 在 P 的每个面（任何维度）上的投影组成，但该描述包括大量以高维面为主的面，我不清楚如何处理有效地。

我相信我非常清楚地了解该算法，除了您通过查看分区来查看是否有任何接近的点并创建一个条带，其中条带内的点是候选点的步骤。

但随后该算法规定按它们的 y 坐标对点进行排序，然后检查条带中的其他点以查找是否存在比先前找到的距离更小的距离。这基本上听起来像是你在地带内的蛮力。

例如，以下是《算法导论》所述：

因此，您似乎只是将每个点与所有其他点进行比较以找到最接近的点？那为什么要按y值排序呢？您已经按 x 对它们进行了排序，为什么不用蛮力呢？

嗨，我在这个论坛上做了一些研究，并没有真正找到我的问题的正确答案。我需要用最快的算法解决财务问题。给定 p 组点，每组有 n 个点，我需要找到算法来计算每组点之间的所有最近点。我认为它可以用最近的对算法或最近的邻居来完成，但我不知道如何在少于 o(n^2) 的操作中做到这一点。

现在我正在对整个图执行 Dijkstra 算法，并通过与原始节点的总距离形成节点的最小堆。然后我从堆中删除前 n 个元素。

这让我觉得效率非常低。假设我需要找到 10 个最近的节点，而我的图有超过 100000 个节点。然后在整个图表上执行 Dijkstra 似乎是在浪费时间。但问题是我不确定是否有任何其他方法可以在不计算图中每个节点的最短路径的情况下找到前 10 个最近的节点。

有没有更好的办法？

我一直在考虑最近对问题的一个变体，其中唯一可用的信息是已经计算的距离集（我们不允许根据它们的 x 坐标对点进行排序）。

考虑 4 个点（A、B、C、D）和以下距离：

在这个例子中，我不需要评估dist(B,C)or dist(A,D)，因为可以保证这些距离大于当前已知的最小距离。

1. 是否可以使用这种信息将 O(n²) 减少到 O(nlogn) 之类的东西？

2. 如果我接受一种近似解决方案，是否可以将成本降低到接近 O(nlogn) 的程度？在这种情况下，我正在考虑一些基于强化学习的技术，该技术仅在强化数量达到无限时收敛到真实解决方案，但为小 n 提供了很好的近似值。

3. 处理时间（用大 O 表示法衡量）不是唯一的问题。保留大量先前计算的距离也可能是一个问题。

4. 想象一下这个问题对于一个有 10⁸ 点的集合。

我应该寻找什么样的解决方案？这种问题以前解决了吗？

这不是课堂问题或相关问题。我一直在思考这个问题。

我需要创建一个为每对文档发出一个值的视图（_all_docs 与自身的笛卡尔积）

例如，假设 DB 有 IDa为 , b, c-> 的文档，那么视图应该发出 9 个键aa, ab, ac, ba, ... , cc（假设没有分组）

例如，如果文档是带有坐标的“城市”，则视图会返回成对的城市和它们之间的距离（实际示例更复杂），因此我可以使用_list函数来计算“top10 最近的城市”等等。

这看起来是一个非常简单的任务，但是 Google 和 SO 搜索没有给出任何结果。我在这里错过了一些神奇的关键字吗？

我有两个矩阵 A(m X 3) 和 B(n X 3)；其中 m >> n。

B 中的数字与 A 中的数字具有接近或相等的值。

我想搜索从 A 到 B 中存在的值的最接近的可能值，在搜索结束时，A 将减少到 (n X 3)。

主要有两个问题：

1. 只有 A 中的完整行可以与 B 中的完整行进行比较，其中 A 和 B 的每一列中的数字独立变化。
2. A 和 B 中的数字可能接近小数点后第三位（例如 20.101 和 20.103）

我希望我能清楚地提出我的问题。有人知道matlab中已经存在的任何函数吗？

我有一个像这样的文件：

我想找到这两个数字及其最近的距离。我正在使用 shell 脚本。当时我有：

在下一种情况下，我想考虑两列。x 轴的列和 y 轴的列也是如此。这就像最近的一对点问题。我也想得到帮助。

感谢您的帮助！

假设我需要找到从一个 (x,y) 坐标到百万坐标数组中每个坐标的欧几里德距离，然后选择距离最小的坐标。

目前我循环通过百万元素数组，计算跟踪最小值的距离。有没有办法我可以以不同的方式更快地做到这一点。

谢谢