42digest
计算点集直径的实用方法

A Practical Approach for Computing the Diameter of a Point Set

Sariel Har-Peled

arXiv
2025年5月16日

我们提出了一个近似算法,用于计算 ^d 中点集的直径。 新算法对计算给定输入的直径的“硬度”很敏感,对于大多数输入来说,它能够极快地计算确切的直径。 新算法简单、健壮,具有良好的经验性能,可以快速实现。 因此,它似乎是计算/近似直径在实践中选择的算法。

We present an approximation algorithm for computing the diameter of a point-set in ^d. The new algorithm is sensitive to the "hardness" of computing the diameter of the given input, and for most inputs it is able to compute the exact diameter extremely fast. The new algorithm is simple, robust, has good empirical performance, and can be implemented quickly. As such, it seems to be the algorithm of choice in practice for computing/approximating the diameter.