Given list of 2d points, find the point closest to all other points

Question

Input: list of 2d points (x,y) where x and y are integers.

Distance: distance is defined as the Manhattan distance. 
    ie:
    def dist(p1,p2) 
         return abs(p1.x-p2.x) + abs(p1.y - p2.y)

What is an efficient algorithm to find the point that is closest to all other points.

I can only think of a brute force O(n^2) solution:

minDist=inf
bestPoint = null
for p1 in points:
    dist = 0
    for p2 in points:
        dist+=distance(p1,p2)
    minDist = min(dist,minDist)
    bestPoint = argmin(p1, bestPoint)

basically look at every pair of points.

Answer 1

Note that in 1-D the point that minimizes the sum of distances to all the points is the median.

In 2-D the problem can be solved in O(n log n) as follows:

Create a sorted array of x-coordinates and for each element in the array compute the "horizontal" cost of choosing that coordinate. The horizontal cost of an element is the sum of distances to all the points projected onto the X-axis. This can be computed in linear time by scanning the array twice (once from left to right and once in the reverse direction). Similarly create a sorted array of y-coordinates and for each element in the array compute the "vertical" cost of choosing that coordinate.

Now for each point in the original array, we can compute the total cost to all other points in O(1) time by adding the horizontal and vertical costs. So we can compute the optimal point in O(n). Thus the total running time is O(n log n).