奥斯汀史密斯

Major: 数学

指导老师: Stefan Tohaneanu

项目名称:

直奔主题! 精确拟合问题

Abstract

假设你正在穿越一个大城市的市中心, 目的是尽可能多地游览这座城市. 如果你列出你最想看的前20家店面, 哪条直线能把你带到最多的景点? 你总能找到这样一条直线吗?

类似的, 考虑图形计算器创建最佳拟合线的方式, 用“最小二乘法”定义“最佳”(1).e. 线性回归问题). 如果我们用一种叫做“精确拟合”的方法来拟合一条直线呢? 在这种方法中，“最佳”线是与最多的点相交的线. 计算这条直线最有效的方法是什么?
寻找最有效的算法来计算这条线是计算几何中的一个开放问题, 称为精确拟合问题. gu等人. 之前已经展示了一个O(min{N^2log(N)， N^2})的二维时间解.

Here, 我们研究了另一种方法，使用行列式的属性来创建一个用c++编码语言实现的新算法. 该算法的时间效率估计为O(N^3)。. 因为这个问题有着广泛的影响, 找到一种有效的算法将对包括编码理论在内的许多领域产生积极的影响.