给定一组点，我如何找到彼此最远的两个点? [英] Given a set of points, how do I find the two points that are farthest from each other?

问题描述

可能重复:
最大线性维度二维点集

我可以计算每个点之间的距离并取最大距离，但是当点数很大(> 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.

这是一个可读性很强的讨论 用于任务的正确 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屋！