Optimal meeting point

I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point and to minimize the time/distance for everyone.

I'm looking for information on that problem, but I've only been able to find advanced paper on this problem.

My questions:

• Is it part of a more general problem?

• Is graphs the best way to implement it? (the nodes are the possible meeting points, the edges are the possible roads for example..) How do current programs work, for example using maps like Google Map?

• Is it P or NP?

My difficulties to understand the problem and to find more informations about it

I know it's a bit vague, but I've got some difficulties because I don't know much about this kind of problems. I was just wondering one day "how to find the best restaurant in terms of distance to meet with some friends". I don't know what is mathematically the parameter that I should minimize to be "fair" (the sum of the distances of the $n$ individuals to the meeting point? The average?...).

Response to comment: (assuming that using graph is the best way to do it)

In input, we have a graph and we have the $n$ individuals (a list of $n$ vertices if we implement it with graphs, even if it means to add them to the graph), and in output, we get the optimal meeting point (i.e. the vertex which is at the minimal distance from all the $n$ individuals).

There are two kinds of minimizing in this sense,

• the first is to minimize the sum of the distances.

• the second is to minimize the maximum distance (finding a restaurant where the farthest friend is as near as possible).

In both cases it's not NP-Hard, since you can calculate all-pairs shortest path in $O\left(N^2\log\left( E+N \right)\right)$, sum up the distances from each restaurants to all friends and compare the sums.

Ps A special case is points laying on a line segment. The solution to the first type will be the restaurant dividing the vertices in two most-possible equal groups (has so many friends on its left as many friends on its right), the reason this works can be derived from the fact that median minimize absolute deviation.
The solution to the second problem is trivially the nearest restaurant to the middle point between the two farthest friends.

Ps2 In trees you can solve the second type using two DFSes to find the two farthest points and then choose the point in between them minimizing the distance to both of them.

The second type however, can be done in trees using a bfs traversal from leaves, counting the number of friends and distance to them in subtree of each node. Then a second bfs from the root of the tree summing all the numbers up.

StackExchange Computer Science Q#94019, answer score: 4