An Optimal Algorithm for the Farthest Pair Problem of a Point Set
QU JiLin1,2, KOU JiSong1, LI MinQiang1
Institute of System Engineering, Tianjin University, Tianjin 300072 Department of Computer Science and Engineering, Shandong University of Finance, Jinan 250014
Abstract：An optimal algorithm for the farthest pair problem is presented in this paper. Given a set of n points in the plane, this paper proposes a new method to find the antipodal pairs of the convex hull of the point set. Using this method, the farthest pair problem can be solved in O(nlogn) time.
曲吉林，寇纪淞，李敏强. 一种确定点集最远点对的最优算法[J]. 模式识别与人工智能, 2006, 19(1): 27-30.
QU JiLin, KOU JiSong, LI MinQiang. An Optimal Algorithm for the Farthest Pair Problem of a Point Set. , 2006, 19(1): 27-30.
[1]Daniele V F, Marco P. On Computing the Diameter of a Point Set in High Dimensional Euclidean Space. Theoretical Computer Science, 2002, 287(2): 501-514 [2] Lee D T, Preparata F P. Computational Geometry: A Survey. IEEE Trans on Computers, 1984, 33(12): 1072-1101 [3] Preparata F P, Shamos M I. Computational Geometry: An Introduction. New York, USA: Springer-Verlag, 1985
2006, Vol. 19 
