以平行线段为模型的非精确数据凸包问题研究

现实应用中，计算机处理的数据往往是非精确的。对于非精确的输入数据，一般使用线段，圆和正方形等模型表示。对以平行线段代表非精确数据的模型研究非常重要，因为这种非精确数据模型是解决其他更复杂模型的基础1]。loffler等1]给出了一种算法，可以在时间O（n³）内求出以竖直平行线段表示的非精确数据的最大面积凸包。但是该算法对于任何输入数据计算量都是一样，而现实生活中的非精确数据往往不是完全没有规律的，比如来自同一设备采样的数据的误差范围是一致的。首先给出了一种新的算法，可以在O（nlog（n））时间内求出具有相同取值范围的非精确数据的最大面积凸包，同时研究了输入数据是n个非精确数据和m个退化为精确数据的非精确数据如何求最大面积凸包的问题。如果把这些已经退化的非精确数据仍然看作非精确数据，套用文献1]的算法时间复杂度将会是O（（n+m）³）。针对这种情况给出了一种算法，算法时间复杂度为O（n³+nm）。

New algorithms for convex hull of maximum area based on parallel line segment

The imprecise inputs can be assumed as segments,circles or squares.It is very important to study the model of parallel line segments for imprecise inputs because it is the fundament to solve other models.An algorithm for the largest area of the convex hull with the assumption of parallel line segments is presented in reference1].The running time of the algorithm is O(n)3. But in many real life cases,there are some patterns for error ranges.For example,the error ranges are the same.In this paper a new algor...