Austin Smith

Major: Mathematics

Faculty Advisor: Stefan Tohaneanu

Project Title:

Getting to the Point! The Exact Fitting Problem

Abstract

Suppose you were traveling through a downtown urban sprawl of a large city, aiming to see as much of the city as possible. If you listed out the top twenty storefronts you wanted to see, what straight line would take you to the largest number of attractions? Could you always find such a straight line?

Similarly, consider the way a graphing calculator creates a line of best fit, defining “best” by the “least squares approach” (i.e. the linear regression problem). What if instead we fit a line using something called the “exact fitting” method? In this method, the “best” line is the one that intersects the largest number of points. What is the most efficient method to calculate this line?
Finding the most efficient algorithm to compute this line is an open question in computational geometry, known as the exact fitting problem. Guibas et al. have previously shown an O(min{N^2log(N), N^2}) time solution in two dimensions.

Here, we examine an alternative approach using properties of determinants to create a new algorithm implemented in the C++ coding language. An estimate for the time efficiency of the algorithm can be conjectured to be O(N^3). Because this problem has widespread implications, finding an efficient algorithm would have positive impacts on numerous fields including coding theory.