给定一组点，我怎么觉得这两个点是彼此相距最远？ [英] Given a set of points, how do I find the two points that are farthest from each other?

问题描述

可能重复：
  最大线性尺寸的2D点集

我可以计算出每个点之间的距离，并采取最大的，但这并不听起来像一个非常有效的方式来做到这一点的时候还有点大（> 1000）号。

I could compute the distance between each point and take the largest but that doesn't sound like a very efficient way to do it when there are a large (> 1000) number of points.

注：这是iPhone，所以我没有一吨的处理能力的

推荐答案

你问来计算的直径组。的标准技术是先计算的凸包，从而降低了问题找到一个凸多边形的直径。即使在你不排除任何点的情况下，这一附加信息正是我们所需要的，以有效地解决这个问题。然而，寻找一个凸多边形的直径是不完全琐碎;一些发表的论文与这一任务的算法变成是不正确的。

You're asking to compute the diameter of the set. The standard technique is to first compute the convex hull, which reduces the problem to finding the diameter of a convex polygon. Even in the case where you don't eliminate any points, this added information is exactly what's needed to solve the problem efficiently. However, finding the diameter of a convex polygon is not entirely trivial; several published papers with algorithms for this task turn out to be incorrect.

下面是一个<一href="http://www.facweb.iitkgp.ernet.in/~arijit/courses/autumn2006/cs60001/lec-compugeo-3.pdf">fairly可读讨论一个正确的O（n）的算法为任务（其中n是凸包点的数目）。

Here's a fairly readable discussion of a correct O(n) algorithm for the task (where n is the number of points in the convex hull).

另外，还要注意的iPhone是没有的是的限制;即使是完全天真的算法浓墨重彩的实现可以在不到十分之一秒处理1000点。当然，使用正确的算法会让你去得更快=）

Also, note the the iphone isn't that limited; a carefully written implementation of even the completely naive algorithm can handle 1000 points in less than a tenth of a second. Of course, using the correct algorithm will let you go much faster =)

这篇关于给定一组点，我怎么觉得这两个点是彼此相距最远？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！