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)

Was ist ein effizienter Algorithmus, um den Punkt zu finden, der allen anderen Punkten am nächsten ist?

Ich kann mir nur eine Brute Force O (n ^ 2) -Lösung vorstellen:

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)

Betrachten Sie grundsätzlich jedes Punktepaar.