一种确定点集最远点对的最优算法

曲吉林; 寇纪淞; 李敏强

模式识别与人工智能 ›› 2006, Vol. 19 ›› Issue (1) : 27-30.

论文与报告

一种确定点集最远点对的最优算法

作者信息 +

An Optimal Algorithm for the Farthest Pair Problem of a Point Set

Author information +

History +

摘要

提出了一种确定点集最远点对的最优算法.对平面内 n个点的点集,在求出其凸包后,利用求对跖点对的方法确定凸包的最远点对,从而得到点集的最远点对.整个算法的时间复杂性为 O(nlogn).

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.

导出引用

曲吉林 , 寇纪淞 , 李敏强. 一种确定点集最远点对的最优算法. 模式识别与人工智能. 2006, 19(1): 27-30

QU JiLin , KOU JiSong , LI MinQiang. An Optimal Algorithm for the Farthest Pair Problem of a Point Set. Pattern Recognition and Artificial Intelligence. 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

PDF(290 KB)

977

Accesses

Citation

Detail

段落导航

摘要
Abstract
关键词
Key words
引用本文
参考文献

Received	Revised	Published
2004-10-20	2005-03-03	2006-02-25
Issue Date
2015-10-26

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

{{custom_fnGroup.title_cn}}

脚注

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

摘要

Abstract

关键词

Key words

引用本文

{{custom_sec.title}}

{{custom_sec.title}}

参考文献

{{custom_fnGroup.title_cn}}

脚注