论文标题
算法在具有OEXP（N）复杂性的E2中找到精确的最大距离：分析和实验结果
Algorithm for Finding an Exact Maximum Distance in E2 with Oexp(N) Complexity: Analysis and Experimental Results
论文作者
论文摘要
本文描述了一种具有O（N）预期复杂性的新颖，快速，简单，可靠的算法，该算法可以减少在E2中找到两个点的最大距离所需的运行时间。通常，对于E3情况，它可以很容易地修改。已提出的算法已在较大的不同数据集上进行了实验评估，以验证它并证明其预期的特性。实验证明了基于蛮力，凸壳或凸壳直径接近的基于标准算法的算法比标准算法的优势。当处理中和大数据集时，所提出的算法对应用程序进行了显着加速。它的速度比标准蛮力算法快10000万倍。 E2中随机分布点的点比凸直径计算快4倍。随着处理的点数的增长，提出的算法的加速增长。
This paper describes a novel and fast, simple and robust algorithm with O(N) expected complexity which enables to decrease run time needed to find the maximum distance of two points in E2. It can be easily modified for the E3 case in general. The proposed algorithm has been evaluated experimentally on larger different datasets in order to verify it and prove expected properties of it. Experiments proved the advantages of the proposed algorithm over the standard algorithms based on the Brute force, convex hull or convex hull diameters approaches. The proposed algorithm gives a significant speed-up to applications, when medium and large data sets are processed. It is over 10 000 times faster than the standard Brute force algorithm for 10 mil. points randomly distributed points in E2 and over 4 times faster than convex hull diameter computation. The speed-up of the proposed algorithm grows with the number of points processed.
