/prog/ CHALLENGE 2011

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

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.

assume |v| > 1.
Text solution:
K-1 circles. Min radius = min distance between two points of set V.

FOIC solution

min_distance = your_mom.weight
for p1, p2 in zip(V,V):
   t = p1 - p2
   min_distance =  min(min_distance, sqrt(t.x*t.x + t.y*t.y))

# print radius
print "Min radius: %f" % min_distance

# print N-1 circles
for i,p in enumerate(V[1:])
   print "%d st/nd/th circle: %s" % (i,p)

This solution is optimal.
Proof:

1) At most N-1 circles possible
2) This mean that at least one circle should cover two points.
3) This mean that at least one circle will have point in center and point on at least radius distance.
4) Since we have N-1 circles, each point is either center of circle or covered by other circle
5) Radius can not be decreased: we can not add another circle and we decreasing radius will mean that one point(which is not center of circle) is not covered.
QED