Euclidean K-Center Problem

Question

My google searches have brought me to rather long papers explaining the Euclidean K-Center problem.

Can someone please provide a high-level explanation?

Thanks.

score 3 · Accepted Answer · answered Jan 16 '13 at 18:10

3

Given $n$ houses represented as points in the plane, find the optimal location of $k$ firestations to protect them, optimal in the sense that these locations minimimize the furthest distance between a house and a firestation. For $k=1$, the optimal is the center of the minimum circumscribing circle.

Finding an exact solution is NP-hard, but there are approximation algorithms, unfortunately none that can beat a factor of $2$.

answered Jan 16 '13 at 18:10

Joseph O'Rourke

30,327

If the houses are randomly placed, then the center is still the optimum? – Kevin Meredith Jan 16 '13 at 18:25
Yes, random placement is not directly relevant. – Joseph O'Rourke Jan 17 '13 at 00:38

Euclidean K-Center Problem

1 Answers1