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

• 作者: 罗军 鞠汶奇
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 非精确数据 计算几何 凸包
• 年，卷（期）: 2010,（1）
• 所属期刊栏目: 图形、图象、模式识别
• 页码范围: 154-159
• 页数: 6页
• 分类号: TP301.6
• 字数: 5733字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.01.047

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗军	中国科学院深圳先进技术研究院	51	222	8.0	12.0
2	鞠汶奇	中国科学院计算技术研究所	1	0	0.0	0.0