Name: Anonymous 2011-01-15 7:15
Given a set V of N 2 dimensional points and a number k (0 < k < N) find k circles which have the same radius r and the centers in V and cover all the N points in V and r must be the smallest possible.
An equivalent formulation of the problem would be given a point x and a finite set of points S we have dist(x, S) = min{dist(x,y) | y ∈ S} and radius(S) = max{dist(x, S) | x ∈ V}. You must determine a subset S ⊆ V, |S| = k which minimizes radius(S).
An equivalent formulation of the problem would be given a point x and a finite set of points S we have dist(x, S) = min{dist(x,y) | y ∈ S} and radius(S) = max{dist(x, S) | x ∈ V}. You must determine a subset S ⊆ V, |S| = k which minimizes radius(S).