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.
[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 
