Minimizing total distance to a point from a set of points I've read about a problem:


  There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal.


I've written a Monte-Carlo algorithm, but that can't be the optimal approach.

Is there a solution other than approximating the position with Monte-Carlo method? Especially by using a graph or is that a wrong approach?

Is there a way to calculate the optimal position?

What is the name of this problem?
It's a two-dimensional facility location problem. In this case, the optimum location is the centre of gravity (also known as the barycentre or centroid) of the locations of the houses, which is easily calculated from their co-ordinates.