Given a 2D point and an array of 2D points find the closest point in the array to the input point.

def closest(Point, Points):
	returns the point in Points that is closets to Point.

Super easy question was able to code O(n) solution immediatly. Then a follow up was asked of what if this function was called a lot and the list of Points didn't change. I suggested you could use a cache and if you had already calculated the closest point for point A then your solution would be O(1). It seems there was another way to do this without caching that would have a runtime better than O(n), any ideas? Some sort of sorting the points I would imagine.