以平行线段为模型的非精确数据的最大面积凸包问题的算法研究
现实应用中,计算机处理的数据往往是非精确的。对于非精确的输入数据,一般使用线段,圆和正方形等模型表示。对以平行线段代表非精确数据的模型研宄非常重要,因为这种非精确数据模型是解决其他更复杂模型的基础,loffler”1等给出了一种算法,可以在时间O(n3)内求出以平行线段表示的非精确数据的最大面积凸包。但是该算法对于任何输入数据计算量都是一样,而现实生活中的非精确数据往往不是完全没有规律的,比如来自同一设备采样的数据的误差范围是一致的。本为首先给出了一种新的算法,可以在O(nologn)时间内求出具有相同取值范围的非精确数据的最大面积凸包,同时本文研宄了输入数据是n个非精确数据和m个退化为精确数据的非精确数据如何求最大面积凸包的问题。如果把这些已经退化的非精确数据仍然看做非精确数据,套用”1”的算法,时间复杂度将会是O((n+m)3)。本文针对这种情况给出了一种算法,算法时间复杂度为O(n3+(n+m)log(m)+m)。
非精确数据 平行线段 计算几何 最大面积 凸包问题算法
鞠汶奇 罗军
中国科学院计算技术研究所 北京 100080 中国科学院深圳先进技术研究院,广东 深圳 518055 中国科学院研究生院,北京 100049 中国科学院深圳先进技术研究院,广东 深圳 518055
国内会议
厦门
中文
119-129
2009-08-24（万方平台首次上网日期，不代表论文的发表时间）