求多边形距离最大的两个顶点,该如何解决

求多边形距离最大的两个顶点
请问大家有没有比两两比较更快的方法求出多边形距离最大的两个顶点? 两两比较是N平方的工作量, 不好. 谢谢!

------解决方案--------------------
学习了，最远点对和最近点对解法是一样的吗？
搜一下“旋转卡壳法”也许有点用吧，可以求出凸包的最远点对。
------解决方案--------------------
最近/最远点对的问题,最经典解法肯定是不一样.
周培德,那本<<算法几何>>上有最近点对的问题n*logn.

但是如果都采用用"遗传算法"是必定有接近最优解的 .
而且在实际问题中,干扰因素越多,可能更实用些.
不过."遗传算法"不是传统意义上的最小时间,空间复杂度的算法,
可以说是一种"办法",而不算是"算法".
 
------解决方案--------------------
if (n较小) {用直接法寻找最近点对
R e t u r n ; }
// n较大
将点集分成大致相等的两个部分A和B
确定A和B中的最近点对
确定一点在A中、另一点在B中的最近点对
从上面得到的三对点中，找出距离最小的一对点


class Point1 {
friend float dist(const Point1&, const Point1&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&,float&);
friend void main();
p u b l i c :
int operator<=(Point1 a) const
{return (x <= a.x);}
p r i v a t e :
int ID; // 点的编号
float x, y; // 点坐标
} ;
class Point2 {
friend float dist(const Point2&, const Point2&);
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&, Point1&, float&);
friend bool closest(Point1 *, int, Point1&, Point1&, float&);
friend void main();
p u b l i c :
int operator<=(Point2 a) const
{return (y <= a.y);}
p r i v a t e :
int p; // 数组 X中相同点的索引
float x, y; // 点坐标
} ;
 
------解决方案--------------------
最远和最近点对的方法有不小的区别，不过都是n*log(n)的。

凸壳也只能得到一个点集, 如何得到需要的两点呢? 难道最后再把凸壳的顶点两两比较 ? 那如果多边形本来就是凸的那不就失败了吗?

找出凸包之后，再找最远点对的话是O(n)的，设到A最远的点为D，那么到A顺时针方向的下一个点A'最远的点，一定是D或D的顺时针方向后面的点。这样检测的话，每个点都只被检查2遍。