Find the minimum number of points to draw a circle of a particular radius to that gathers all the given points

Question

Hi,

I've a set of points marked in a graph. How do I find the coordinates (minimum number) to draw circles of specific radius so that all the points are gathered within the circles drawn.

For e.g. I've points (5, 3), (2, 4), (1, 5), (8, 8), (9, 6), (6, 1), (1, 3) and I'll be drawing circles of radius 2 cms. How many minimum number of circles and at which points I should be drawing them, so that all the points are inside at least within one of the circles drawn. (I could have explained better if it was possible for me to attach an image, but help me out, please!).

Thanks,

Venkat

Answer 1

This is similar to the Disk Coverage Problem (studied for finding best wireless coverage for example). Don't know what the algorithm might be, but you might start with disks centred on each point (the worst case) then move the disk centres towards neighbouring points and delete disks when a point is in two disks. Though the points are sparse, it probably is still an NP-complete problem, like a Traveling Salesman problem.

Answer 2

by 2 factors, infinitely many. (think of the two factors as endpoints of a diameter, then "push" the circle down and improve its length so as that it nonetheless includes the two factors.) The third (noncollinear) element determines the circle uniquely, so basically one. FYI, here is why. The arbitrary equation for a circle is Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 which has six parameters. each and every element has 2 coordinates (x and y). 2 factors have 4 coordinates entire, below six, which leaves infinitely many the thank you to end the circle equation. 3 factors have six coordinates entire -- in the event that they artwork (it extremely is the noncollinear requirement), then they specify all six parameters of the equation.

Answer 3

i would use graph theory to solve this.



Create a graph with the vertices defined by the points, and edges drawn between points you can put in one circle with radius 2.



Then, i would solve the problem as a Shortest path problem.

Answer 4

I don't think there is a unique answer to this question, but I don't really understand the question. I suggest you post an image to http://tinypic.com/ and link to it here, and try for the "better explanation".

Answer 5

Three Circles of radius 2cm will be minimum required.

They will have Centres at (1,4);(5,2);(8,7)



First circle contains (1,3);(1,5);(2,4)

Second contains (5,3);(6,1)

Third contains (8,8);(9,6)