Optimal meeting point

Question

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).

Answer 1

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.

Answer 2

narek gives the polynomial-time algorithm. The more general problem is the facility location problem. This includes several problems but the basic idea is that you want to know where to build your restaurants (plural) to minimize the distance people need to travel (with multiple restaurants, we just assume that people want to eat somewhere, not that they all want to eat together) or to compute how many restaurants you need so that everybody is within some distance of one.

As for what metric to optimize, note that minimizing the sum is the same thing as minimizing the average, which is just the sum divided by $n$. The main alternative is to minimize the maximum distance anyone needs to travel. These can have rather different effects. Suppose you have 99 people in Los Angeles and one in New York. If you minimize the average distance, the one guy in New York flies to LA; if you minimize the maximum distance, everybody schleps over to somewhere like Omaha.

It's not my area of research but I've been to plenty of seminars on it, which suggests that it's an active field with plenty of open problems. There should be plenty for you to do, at whatever level you want to work at.