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).
>>15 Is this homework or something?
Yes, but I didn't post that. Someone at my school must be really desperate. Plus I'll probably write the solution in Racket. I just don't have any idea yet how to do this whole thing.
>>16
I don't think you'll find an efficient algorithm that is guaranteed to find the optimal solution. The approximation follow-up question hints at that, too. You'll just have to brute force it somehow.
>>17
I doubt it's a trick question. Now the greedy algorithm is simple but finding the optimal solution every time, I can't figure it out :(
Name:
Anonymous2011-01-18 0:02
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 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
Binary search on R.
After that you can do some exponential DP or some shit, hell if I know. I'm fairly sure the problem of determining whether you can solve this with a fixed R is not equivalent to the vertex cover problem, though.
In particular, I was thinking of the graph G=(V,E) where V=V from the problem statement and E={(v1,v2) in VxV | dist(v1,v2)<=R}. If you look for a k-vertex cover on this graph you will get the wrong answer for the following input:
V = {(0,0),(1,0),(2,0),(3,0),(4,0),(5,0)} K=2.
The right answer is R=1 with circles at (1,0) and (4,0), but if we think about the problem as a quest for a k-vertex cover we'll fail because the edge ((2,0),(3,0)) won't be incident on either of our chosen vertices.
If the guy who suggested k-vertex cover had something else in mind I'd love to hear it.
Isn't R the radius? How would you do a binary search on it?
Name:
Anonymous2011-01-18 14:39
>>29
I can do a binary search on R but I have to choose k points. I can find the optimal R for those k points but how do I know those points are the best I could have possibly chose?