论文标题
减少二维数据以加速凸船体计算
Reduction of Two-Dimensional Data for Speeding Up Convex Hull Computation
论文作者
论文摘要
提出了用于计算二维数据点的凸壳的增量方法。该算法不是输出敏感的，并且成本在输入处的数据点大小上是线性的。 Graham的扫描仅应用于数据集极端表示的数据点的子集。将点分类为极端，与模块距离成比例，大约是假想点的内部，与被假定为原点的数据集的凸面或偏置坐标中心的凸面。数据的一个子集通过终止时到达，直到每箱未观察到最大点不变的事件，因为迭代和指数减小的间隔。
An incremental approach for computation of convex hull for data points in two-dimensions is presented. The algorithm is not output-sensitive and costs a time that is linear in the size of data points at input. Graham's scan is applied only on a subset of the data points, represented at the extremal of the dataset. Points are classified for extremal, in proportion with the modular distance, about an imaginary point interior to the region bounded by convex hull of the dataset assumed for origin or center in polar coordinate. A subset of the data is arrived by terminating at until an event of no change in maximal points is observed per bin, for iteratively and exponentially decreasing intervals.
