Let me clarify: Given a scatterplot of some given number of points n, if I want
ID: 653012 • Letter: L
Question
Let me clarify:
Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, narrowing my choices down to some small, constant number of points nearby.
Yet, in programming, given a set of points n, in order to find the closest point to any one, it requires checking every other point, which is ${cal O}(n)$ time.
I am guessing that the visual sight of a graph is likely the equivalent of some data structure I am incapable of understanding; because with programming, by converting the points to a more structured method such as a quadtree, one can find the closest points to $k$ points in $n$ in $kcdotlog(n)$ time, or ammortized ${cal O}(log n)$ time.
But there is still no known ${cal O}(1)$ ammortized algorithms (that I can find) for point-finding after data restructuring.
So why does this appear to be possible with mere visual inspection?
Explanation / Answer
The reason is that the data has been put in a "data structure" optimized for this query and that the preprocessing time in preparing the graph should be included in your measured times which is proportional to the number of dots, giving a O(n) complexity right there.
If you put the coordinates in a table listing X and Y coordinates of each point you would require a much larger mental effort to calculate the distances between points, sort the list of distances and choose the smallest.
As an example of a query not working well visually, would be to look at the night sky and - based on your view only and a table of coordinates of each star - locate the closest star to Earth or which astrological sign has the smallest distance between the stars it consists of. Here you would need a zoomable and turnable 3D model in order to determine this visually, where a computer would consider this to be essentially the same problem as your original.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.