Homework 16: Nearest Neighbor Search
This problem comes to us from Sean, one of our members.
Write a program that reads in a list of points from a file. Your program will also take in some target point (probably on the command line). The program will print out the point from the input file that is closest to the target point.
$ ./nearest 10 20 < all_points.txt
Point (12, 16) is the closest.
The points are pairs of x and y coordinates. The format of the file, your command-line, and your output is up to you.
The points are in the Euclidean space R^2, but you do not have to use Euclidean distance. You may choose to use something else (like a variation on Manhattan/Taxi distance) if it makes your algorithm faster or use less memory.
Here are some additional guidelines:
- The x and y coordinates should be between 0 and 600
- The x and y coordinates should be integers
- There may be up to 1000 points in the file
Pay careful attention to space and time requirements of your algorithm. Sean would like to use your solution on his phone if it is small and fast enough.
Bring your solution to our July meeting.
Feel free to discuss the problem or any other topics you are interested in on our mailing list (accessible via our Meetup Group).