一种平面数据直径的快速近似算法及其推广

• 作者: 朱浩楠 林珈音 贾小芃
• 来源期刊: 数学建模及其应用
• 学科: 数学
• 关键词: 平面数据直径 近似算法 高维推广 计算几何
• 年，卷（期）: 2020,（2）
• 所属期刊栏目: 中学数学建模论坛
• 页码范围: 83-90
• 页数: 8页
• 分类号: O29
• 字数: 6669字
• 语种: 中文

摘要

提出一个计算平面数据直径的快速近似算法,其时间复杂度为O(N+1/ε).该算法和现有的近似算法结合可推广至高维情形,其时间复杂度为O(Nε-d-2/2+ε-d/2).同时,对Graham扫描法进行了改进,使总用时和内存消耗减少,算法的时间复杂度同样可达到理论下限O(N logN).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林珈音		1	0	0.0	0.0
2	贾小芃		1	0	0.0	0.0
3	朱浩楠		3	0	0.0	0.0