|
|
|
| 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.
|
|
Received: 20 October 2004
|
|
|
|
|
|
[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 
