School of Engineering, London South Bank University, London, United Kingdom.
School of Electronics and Computer Science, University of Westminster, London, United Kingdom.
PLoS One. 2019 Feb 22;14(2):e0212189. doi: 10.1371/journal.pone.0212189. eCollection 2019.
This paper presents a method to reduce a set of n 2D points to a smaller set of s 2D points with the property that the convex hull on the smaller set is the same as the convex hull of the original bigger set. The paper shows, experimentally, that such reduction accelerates computations; the time it takes to reduce from n down to s points plus the time of computing the convex hull on the s points is less than the time to compute the convex hull on the original set of n points. The method accepts 2D points expressed as real numbers and thus extends our previous method that required points as integers. The method achieves a percentage of reduction of points of over 90% in a collections of four datasets. This amount of reduction provides speedup factors of at least two for various common convex hull algorithms. Theoretically, the reduction method executes in time within O(n) and thus is suitable for preprocessing 2D data before computing the convex hull by any known algorithm.
本文提出了一种将一组 n 个 2D 点减少到 s 个 2D 点的方法，使得较小集合的凸包与原始较大集合的凸包相同。本文通过实验表明，这种减少可以加速计算；从 n 减少到 s 点所需的时间加上在 s 点上计算凸包的时间小于在原始 n 点集合上计算凸包的时间。该方法接受表示为实数的 2D 点，因此扩展了我们之前要求点为整数的方法。该方法在四个数据集的集合中实现了超过 90%的点减少率。这种减少量为各种常见的凸包算法提供了至少两倍的加速因子。从理论上讲，减少方法的执行时间在 O(n) 以内，因此适合在使用任何已知算法计算凸包之前对 2D 数据进行预处理。
